双指针

• 两个指针的起始点

面试题 02.02. 返回倒数第 k 个节点

剑指 Offer 22. 链表中倒数第k个节点

• 习惯于k++, k值已知时，k--更优。
• 不需要返回head时，可以修改head值。

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* first=head;
        int i=0;
        while(i<k && first->next != NULL)
        {
             first=first->next;
             i++;
        }
        ListNode* second=head;
        while(first != NULL)
        {
            first=first->next;
            second=second->next;
        }
        return second->val;
    }
};

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* second=head;
        while(k--)
            head=head->next;

        while(head != NULL)
        {
            head=head->next;
            second=second->next;
        }
        return second->val;
    }
};

19. 删除链表的倒数第N个节点

面试题 02.04. 分割链表

86. 分隔链表

141. 环形链表

• while判断条件应该先判断在fast，在判断fast->next, 否则访问空指针。
• 双指针的起始点可以相同

class Solution {
public:
    bool hasCycle(ListNode *head) {
         if(head ==NULL || head->next == NULL)
            return false;   //这两行可省略。
        ListNode* slow=head;   //双指针的起始点可以相同
        ListNode* fast=head->next;
        while(fast !=NULL && fast->next !=NULL ){
           if(slow == fast)
            return true;
           slow=slow->next;
           fast=fast->next->next;
        }
        return false;
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow=head;   //双指针的起始点可以相同
        ListNode* fast=head;
        while(fast !=NULL && fast->next !=NULL ){
           slow=slow->next;
           fast=fast->next->next;
           if(slow == fast)
            return true;
        }
        return false;
    }
};

61. 旋转链表

• 问题出在边界条件上。先while判断，还是先i自减。

int k=3;
while(k--)
   cout<<k;
//输出为2，1，0

int k=3;
while(--k)
   cout<<k;
//输出为2，1

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
          return head;
        ListNode* new_end=head;
        ListNode* count=head;
        int n=1;
        while(count->next!=NULL){
            count=count->next;
            n++;
        }
        count->next=head;
        int move=n-k%n;
        while(--move){
            new_end=new_end->next;
        }
        ListNode* new_head=new_end->next;
        new_end->next=NULL;
        return new_head;
    }
};

234. 回文链表