习题3
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。oj链接
这里我们就要介绍一下快慢指针了。通过快慢指针我们可以解决很多问题，以后都会用到。
那么什么是快慢指针呢？
顾名思义，快慢指针就是通过两个不同指针步长的不同来遍历链表。
这道题我们让一个指针走两步，一个指针走一步，当快指针指向空或快指针的next指向空的时候，慢指针指向位置就是中间节点位置。
struct ListNode* middleNode(struct ListNode* head) { struct ListNode*slow=head,*fast=head; while(fast!=NULL&&fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } return slow; }
衍生题1：
输入一个链表，输出该链表中倒数第k个结点。oj链接
其实也是快慢指针的思想，只是这里不是步长的不同，而是起点不同：
要寻找倒数第k个节点，就让快指针的起点在慢指针的后k步。当快指针指向空的时候，慢指针就指向倒数第k个节点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* slow=pListHead; struct ListNode* fast=pListHead; while(k--) { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }
衍生题2：
给定一个链表，判断链表中是否有环。oj链接
这道题也是用快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
那么，为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
代码如下：
bool hasCycle(struct ListNode *head) { struct ListNode*fast=head,*slow=head; if(head==NULL||head->next==NULL) { return false; } fast=fast->next; while(fast!=slow) { if(fast==NULL||fast->next==NULL) break; fast=fast->next->next; slow=slow->next; } if(fast==slow) return true; return false; }
习题4：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的oj链表
这道题引入了哨兵位，也就是空的头节点。其实，对于链表尾插的时候，需要判断是否为空，比较麻烦，只要我们创建一个空的头节点就可以避免很多情况。
链表在头插的时候我们不需要头节点；
链表在尾插的有空的头节点会更方便。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*tail=newnode; tail->next=NULL; while(list1&&list2) { if(list1->val<list2->val) { tail->next=list1; tail=list1; list1=list1->next; } else { tail->next=list2; tail=list2; list2=list2->next; } } if(list1) tail->next=list1; if(list2) tail->next=list2; return newnode->next; }
习题5：
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。oj链接
这道题我们创建两个新链表（带有哨兵位的空头节点），小于的尾插到一个链表，大于的尾插到另外一个链表，最后将他们连起来即可。
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode*greaternode=NULL; struct ListNode*lessnode=NULL,*cur=pHead; struct ListNode* gtail=greaternode,*ltail=lessnode; while(cur!=NULL) { if(cur->val>=x) { gtail->next=cur; gtail=cur; cur=cur->next; gtail->next=NULL; } else { ltail->next=cur; ltail=cur; cur=cur->next; ltail->next=NULL; } } ltail->next=greaternode->next; return lessnode->next; } };
总结
还是那句话，数据结构需要多画图，并且对各种情况要有十足的把握才能做对题目。
