单链表的解题套路

​ 本文主要讲解了常见的单链表处理方法

定义单链表数据结构

 // 第一种 
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) {}
  };
 // 第二种
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 虚拟头节点
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        ListNode *p1 = list1, *p2 = list2;
        while(p1 != nullptr && p2 != nullptr){
            // 比较p1和p2两个指针
            // 将值较小的节点接到p指针
            if(p1->val > p2->val){
                p->next=p2;
                p2=p2->next;
            }else{
                p->next=p1;
                p1=p1->next;
            }
            // p指针不断前进
            p=p->next;
        }
        // 合并后合并后list1和list2最多只有一个还未被合并完，
        // 直接将链表末尾指向未合并完的链表即可
        if(p1!=nullptr){
            p->next=p1;
        }
        if(p2!=nullptr){
            p->next=p2;
        }
        return dummy->next;   
    }

};

复杂度分析

• 时间复杂度：O(n+m)，其中 n和 m分别为两个链表的长度。
• 空间复杂度：O(1)。

代码中⽤到⼀个链表的算法题中是很常⻅的「虚拟头结点」技巧，也就是 dummy 节点。有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if(n == 0) return nullptr;
        // 虚拟头结点
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        // 使用优先级队列
        struct Compare{  // 重写仿函数
            public:
                bool operator()(ListNode* a,ListNode* b){
                    return a->val > b->val; // 小顶堆
                    // return a->val < b->val; // 大顶堆
                }
        };
        priority_queue <ListNode*,vector<ListNode*>,Compare> pq;
        // 将K个链表的头结点加入优先级队列中
        for(ListNode* head : lists){
            if(head != nullptr)
               pq.push(head);
        }
       while(!pq.empty()) {
           ListNode* node = pq.top();
           pq.pop();
           p->next = node;
           // 将链表中剩下的结点依次加入到优先级队列中
           if(node->next != nullptr){
               pq.push(node->next);
           }
           p = p->next;
       }
       return dummy->next;
    }
};

• 时间复杂度：O( n log k)，其中 k 是链表的条数，n是这些链表的节点总数。

返回单链表的倒数第 k 个节点

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        // 快慢指针
        ListNode *fast=head;
        ListNode *slow=head;
        // fast 先走 k 步
        while(k-->0){
            fast = fast->next;
        }
        // fast 和 slow 同时走 n-k步
        while(fast != NULL){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

• 时间复杂度：O( n )。

删除链表的倒数第k个结点

给一个链表，删除链表的倒数第 k个结点，并且返回链表的头结点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int k) {
        // 快慢指针
        ListNode *fast=head;
        ListNode *slow=head;
        // fast 先走 k 步
        while(k-->0){
            fast = fast->next;
        }
        // fast=nullptr表示删除的就是第一个结点(头结点)
        if(fast == nullptr){
            return head->next;
        }
        // fast 和 slow 同时走 n-k+1步
        // 此处找到的是倒数第k+1个结点
        while(fast->next!=nullptr){
            fast=fast->next;
            slow=slow->next;
        }
        // slow 指向倒数第k+1个结点，然后删除第k个结点
        slow->next=slow->next->next;
        return head;
    }
};

• 时间复杂度：O( n )。

链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        // 快慢指针初始化指向 head
        ListNode *fast=head;
        ListNode *slow=head;
        // 快指针⾛到末尾时停⽌
        while(fast != nullptr && fast->next != nullptr){
            fast=fast->next->next;
            slow=slow->next;
        }
        //当链表的长度是奇数时，slow恰巧停在中点位置；如果长度是偶数，slow最终的位置是中间偏右：
        return slow;
    }
};

判断链表是否包含环

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 快慢指针
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast!=NULL && fast->next!=NULL){
            // 快指针⾛两步，慢指针走一步
            fast=fast->next->next;
            slow=slow->next;
            // 快慢指针相遇，说明含有环
            if(slow==fast) return true;
        } 
          // 不含环
        return false;  
    }
};

返回链表中环的入口结点，如果无环则返回NULL。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        // 快指针走到末尾时停止
        while(fast!=NULL && fast->next!=NULL){
            // 快指针走两步，慢指针走一步
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) break;
        }
        if(fast==NULL||fast->next==NULL){
            // fast 遇到空指针说明没有环
            return NULL;
        }
        // 重新指向头结点
        slow = head;
        // 快慢指针同步前进，相交点就是环起点
        while(slow!=fast){
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};

两个链表是否相交

思路：让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相
当于「逻辑上」两条链表接在了⼀起，p1和p2就能达到相交结点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
        ListNode *p1=headA, *p2=headB;
        while(p1!=p2){
            // p1 ⾛⼀步，如果⾛到 A 链表末尾，转到 B 链表
            if(p1==NULL){
                p1=headB;
            }else{
                p1=p1->next;
            }
            // p2 ⾛⼀步，如果⾛到 B 链表末尾，转到 A 链表
            if(p2==NULL){
                p2=headA;
            }else{
                p2=p2->next;
            }
        }
        return p1;
    }
};
//时间复杂度：O(n)。
//空间复杂度：O(1)。

83.删除排序链表中的重复元素 I

//方法一
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr) return nullptr;
        ListNode *p =head;
        while(p->next){
            if(p->next->val == p->val){
                p->next = p->next->next;
            }else{
                p=p->next;
            }
        }
        return head;
    }
};

//方法二
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr) return nullptr;
        ListNode *slow=head, *fast=head;
        while(fast!=nullptr){
            if(fast->val != slow->val){
                slow->next=fast;
                slow=slow->next;
            }
                fast=fast->next;
        }
        slow->next=nullptr;
        return head;
    }
};

82.删除排序链表中的重复元素 II

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr) return nullptr;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *p = dummy;

        while(p->next && p->next->next){
            if(p->next->val == p->next->next->val){
                int tmp = p->next->val;
                while(p->next && p->next->val==tmp){
                    p->next = p->next->next;
                }
            }else{
                p = p->next;
            }
        }
        return dummy->next;
    }
};

反转单链表

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //递归实现反转单链表
         if(pHead==NULL ||  pHead->next==NULL) return pHead; //递归结束条件
         ListNode* Last = ReverseList(pHead->next);
         pHead->next->next = pHead;
         pHead->next = NULL;
         return Last;
    }
};
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //迭代实现
        ListNode* prev = NULL;
        ListNode* curr = pHead;
        while(curr){
            ListNode* next = curr->next;
            //逐个节点反转
            curr->next = prev;
            //更新指针位置
            prev = curr;
            curr = next;
        }
        //返回反转后的头节点
        return prev;
    }
};

反转链表前N个节点

class Solution {
public:
    ListNode* successor = NULL;  //后驱节点
    ListNode reverseN(ListNode* head, int n){
    //将链表的前n个节点反转（n<=链表长度），并返回反转后的链表头节点
        //base case;
        if(n==1){
            //记录第n+1个节点，后面要用
            successor = head->next;
            return head;
        }
        //以head->next为起点，需要反转前n-1个节点
        ListNode* Last = reverseN(head->next,n-1);
        
        head->next->next = head;
        //让反转之后的head节点和后面的节点连接起来
        head->next = successor;
        return Last;
    }
};

反转链表的一部分

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //base case;
        if(left==1){
            //相当于反转前n个元素
            return reverseN(head, n);
        }
        //对于head->next来说，就是反转区间[m-1, n-1];
        head->next = reverseBetween(head->next, m-1, n-1);
        return head;
    }
    //反转前N个节点
    ListNode* successor = NULL;  //后驱节点
    ListNode reverseN(ListNode* head, int n){
    //将链表的前n个节点反转（n<=链表长度），并返回反转后的链表头节点
        //base case;
        if(n==1){
            //记录第n+1个节点，后面要用
            successor = head->next;
            return head;
        }
        //以head->next为起点，需要反转前n-1个节点
        ListNode* Last = reverseN(head->next,n-1);
        
        head->next->next = head;
        //让反转之后的head节点和后面的节点连接起来
        head->next = successor;
        return Last;
    }
};

k个一组反转链表

/**
 * 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* reverseKGroup(ListNode* head, int k) {
        //递归实现
        if(head==nullptr) return nullptr;
        //区间[a, b)包含k个待反转元素
        ListNode* a=head;
        ListNode* b=head;
        for(int i=0;i<k;i++){
            //base case,不足k个,不需要反转
            if(b==nullptr) return head;
            b = b->next;
        }
        //反转前k个元素
        ListNode* newHead = reverse(a, b);
        a->next = reverseKGroup(b, k);
        return newHead;
    }
    //反转a到b之间的节点
    ListNode* reverse(ListNode* a, ListNode* b){
        ListNode* prev = nullptr;
        ListNode* curr = a;
        while(curr!=b){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

143.重排链表

/**
 * 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:
    void reorderList(ListNode* head) {
        //反转链表 + 找链表中间节点 + 交叉合并两个链表
        
        if(head==nullptr) return;
        ListNode* mid = midNode(head);
        ListNode* L1 = head;
        ListNode* L2 = mid->next;
        mid->next = nullptr;
        L2 = reveNode(L2);
        
        mergeNode(L1, L2);

    }
    //反转单链表
    ListNode* reveNode(ListNode* head){
        if(head==nullptr) return nullptr;
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* nxt=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }

    //找链表中间节点
    ListNode* midNode(ListNode* head){
        if(head==nullptr || head->next==nullptr) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    
    //交叉合并两个链表
    void mergeNode(ListNode* a, ListNode* b){
        ListNode* temp_a;
        ListNode* temp_b;
        while(a && b){
            temp_a = a->next;
            temp_b = b->next;

            a->next = b;
            a = temp_a;

            b ->next =a;
            b = temp_b;
        }
    }
};

148.排序链表

/**
 * 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* sortList(ListNode* head) {
        //思路：归并排序

        //base case 
        if(head==nullptr || head->next==nullptr) return head;

        //快慢指针，找到链表中间节点，从中间节点一分为二
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next && fast->next->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        //切链
        fast = slow->next;
        slow->next = nullptr;

        return merge(sortList(head), sortList(fast));
    }

    //合并两个链表
    ListNode* merge(ListNode* a, ListNode* b){
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        while(a && b){
            if(a->val < b->val){
                p->next = a;
                a = a->next;
            }else{
                p->next = b;
                b = b->next;
            }
            p = p->next;
        }

        if(a!=nullptr) p->next = a;
        if(b!=nullptr) p->next = b;

        return dummy->next;
    }
};

234.回文链表

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        //思路：找到链表的中间节点，反转链表的后半部分，和前半部分一一对比
        if(head==nullptr) return true;

        //找到链表中间节点
        ListNode* Mide = midListNode(head);

        //反转后半部分
        ListNode* temp = reveListNode(Mide);

        ListNode* p=head;
        ListNode* q=temp;
        while(q){
            if(p->val != q->val){
                return false;
            }
            p = p->next;
            q = q->next;
        }
        return true;
    }
    //反转链表
    ListNode* reveListNode(ListNode* head){
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
    //寻找链表中间节点
    ListNode* midListNode(ListNode* head){
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

61. 旋转链表

/**
 * 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* rotateRight(ListNode* head, int k) {
        if(head==nullptr || k==0) return head;
        int n=1;       //链表的长度
        ListNode* cur = head;  //尾节点
        while(cur->next){
            cur = cur->next;
            n++;
        }
        k = k%n;
        ListNode* p = head;
        
        for(int i=0;i<n-k-1;i++){ //找到链表的第 n-k 个节点
            p = p->next;
        }

        // 拼接
        cur->next = head;
        head = p->next; //新的头节点
        p->next = nullptr;  //断开

        return head;
    }
};