链表：快慢指针

目录

LeetCode876 链表的中间节点

LeetCode19 删除链表的倒数第N个结点

Leetcode141 环形链表

LeetCode142 环形链表II

LeetCode143 重排链表

---

LeetCode876 链表的中间节点

初始化时快慢指针同时指向head，快指针移动两步，慢指针移动两步。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
};

时间复杂度：O(n)

空间复杂度：O(1) 

LeetCode19 删除链表的倒数第N个结点

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* L=new ListNode(0);
        L->next=head;
        ListNode* fast=head;
        ListNode* slow=L;
        for(int i=0;i<n;i++){
            fast=fast->next;
        }
        while(fast){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        ListNode* res=L->next;
        delete L;
        return res;
    }
};

时间复杂度：O(n)

空间复杂度：O(1) 

Leetcode141 环形链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
};

时间复杂度：O(n)

空间复杂度：O(1) 

LeetCode142 环形链表II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                while(head!=slow){
                    head=head->next;
                    slow=slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

时间复杂度：O(n)

空间复杂度：O(1) 

LeetCode143 重排链表

（1）利用快慢指针找到链表的中间节点

（2）将链表的后半部分翻转

（3）将链表的后半部分插入前半部分

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head){
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* nex=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nex;
        }
        return pre;
    }
    void reorderList(ListNode* head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* last=reverse(slow);
        ListNode* r1=head;
        ListNode* r2=last;
        while(r2->next){
            ListNode* nex1=r1->next;
            ListNode* nex2=r2->next;
            r2->next=r1->next;
            r1->next=r2;
            r1=nex1;
            r2=nex2;
        }
    }
};

时间复杂度：O(n)

空间复杂度：O(1)