每日一题 ---day2 --1-16

• 基础题：逆置/反转单链表，要求只遍历一次链表

解题思路：定义三个指针：

代码：

void  Reverse(ListNode*& l)
{assert(l);ListNode* cur = l;ListNode* tmp = NULL;ListNode* next = NULL;while(cur){ next = cur->_next ;cur->_next = tmp;tmp = cur;cur = next;}l = tmp;
}

• 查找单链表的倒数第K个结点，要求只遍历一次链表。

代码：

ListNode* FindK(ListNode* l,int k)
{if(l == NULL || k == 0)return NULL;ListNode* fast = l;ListNode* slow = l;while(fast && k){fast = fast->_next;--k;}while(fast){fast = fast->_next;slow = slow->_next;}return slow;
}

- 附加题：实现一个Add函数，让两个整数相加，但是不能使用+、- 、* 、/等四则运算符。ps:也不能用++ 、 – 等等。

思路：
可以看出此题要用到位运算，加法的话由两部分组成：
按位相加和，进位；

按位相加且不考虑进位时：1加1结果为0，1加0为1，0加1结果为1，0加0结果为0，通过推理可得这个可用位运算的异或来代替；

进位：主要是当两个数的同一位都为1时，会向它的前一位进1；
两个数的同一位都为1时结果为1；可以用与运算；将结果左移一位相当于进位；

代码实现：

int Add(int a,int b)
{int sum = 0;   //按位和int carry = 0; //进位do{sum = a ^ b;carry = (a & b) << 1 ;a = sum ;b = carry ;}while(b != 0);return sum;
}