单链表的解题套路

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

定义单链表数据结构

 // 第一种 
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) {}
 * };

// Definition for singly-linked list.
type ListNode struct {
    Val int
    Next *ListNode
}

合并两个有序链表

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

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;   
    }

};

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    // 虚拟头节点
    dummy := &ListNode{Val: -1}
    p := dummy
    p1, p2 := list1, list2
    for p1 != nil && p2 != nil {
        // 比较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 != nil {
        p.Next = p1
    }
    if p2 != nil {
        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;
    }
};

import "container/heap"

type MinHeap []*ListNode

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(*ListNode))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    if n == 0 {
        return nil
    }
    // 虚拟头结点
    dummy := &ListNode{Val: -1}
    p := dummy
    // 使用优先级队列
    h := &MinHeap{}
    heap.Init(h)
    // 将K个链表的头结点加入优先级队列中
    for _, head := range lists {
        if head != nil {
            heap.Push(h, head)
        }
    }
    for h.Len() > 0 {
        node := heap.Pop(h).(*ListNode)
        p.Next = node
        // 将链表中剩下的结点依次加入到优先级队列中
        if node.Next != nil {
            heap.Push(h, 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;
    }
};

func kthToLast(head *ListNode, k int) int {
    // 快慢指针
    fast := head
    slow := head
    // fast 先走 k 步
    for k > 0 {
        fast = fast.Next
        k--
    }
    // fast 和 slow 同时走 n-k步
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow.Val
}

• 时间复杂度：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;
    }
};

func removeNthFromEnd(head *ListNode, k int) *ListNode {
    // 快慢指针
    fast := head
    slow := head
    // fast 先走 k 步
    for k > 0 {
        fast = fast.Next
        k--
    }
    // fast=nil表示删除的就是第一个结点(头结点)
    if fast == nil {
        return head.Next
    }
    // fast 和 slow 同时走 n-k+1步
    // 此处找到的是倒数第k+1个结点
    for fast.Next != nil {
        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;
    }
};

func middleNode(head *ListNode) *ListNode {
    // 快慢指针初始化指向 head
    fast := head
    slow := head
    // 快指针⾛到末尾时停⽌
    for fast != nil && fast.Next != nil {
        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;  
    }
};

func hasCycle(head *ListNode) bool {
    // 快慢指针
    fast := head
    slow := head
    for fast != nil && fast.Next != nil {
        // 快指针⾛两步，慢指针走一步
        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;
    }
};

func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    // 快指针走到末尾时停止
    for fast != nil && fast.Next != nil {
        // 快指针走两步，慢指针走一步
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        // fast 遇到空指针说明没有环
        return nil
    }
    // 重新指向头结点
    slow = head
    // 快慢指针同步前进，相交点就是环起点
    for 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)。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    p1, p2 := headA, headB
    for p1 != p2 {
        // p1 ⾛⼀步，如果⾛到 A 链表末尾，转到 B 链表
        if p1 == nil {
            p1 = headB
        } else {
            p1 = p1.Next
        }
        // p2 ⾛⼀步，如果⾛到 B 链表末尾，转到 A 链表
        if p2 == nil {
            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;
    }
};

//方法一
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    p := head
    for p.Next != nil {
        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;
    }
};

//方法二
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    slow, fast := head, head
    for fast != nil {
        if fast.Val != slow.Val {
            slow.Next = fast
            slow = slow.Next
        }
        fast = fast.Next
    }
    slow.Next = nil
    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;
    }
};

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    dummy := &ListNode{Val: -1}
    dummy.Next = head
    p := dummy

    for p.Next != nil && p.Next.Next != nil {
        if p.Next.Val == p.Next.Next.Val {
            tmp := p.Next.Val
            for p.Next != nil && 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;
    }
};

type ListNode struct {
    Val int
    Next *ListNode
}

func ReverseList(pHead *ListNode) *ListNode {
    //递归实现反转单链表
    if pHead == nil || pHead.Next == nil {
        return pHead //递归结束条件
    }
    Last := ReverseList(pHead.Next)
    pHead.Next.Next = pHead
    pHead.Next = nil
    return Last
}

func ReverseList(pHead *ListNode) *ListNode {
    //迭代实现
    var prev *ListNode = nil
    curr := pHead
    for curr != nil {
        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;
    }
};

var successor *ListNode  //后驱节点

func reverseN(head *ListNode, n int) *ListNode {
    //将链表的前n个节点反转（n<=链表长度），并返回反转后的链表头节点
    //base case;
    if n == 1 {
        //记录第n+1个节点，后面要用
        successor = head.Next
        return head
    }
    //以head.Next为起点，需要反转前n-1个节点
    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;
    }
};

var successor *ListNode  //后驱节点

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    //base case;
    if left == 1 {
        //相当于反转前n个元素
        return reverseN(head, right)
    }
    //对于head.Next来说，就是反转区间[m-1, n-1];
    head.Next = reverseBetween(head.Next, left-1, right-1)
    return head
}

//反转前N个节点
func reverseN(head *ListNode, n int) *ListNode {
    //将链表的前n个节点反转（n<=链表长度），并返回反转后的链表头节点
    //base case;
    if n == 1 {
        //记录第n+1个节点，后面要用
        successor = head.Next
        return head
    }
    //以head.Next为起点，需要反转前n-1个节点
    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;
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    //递归实现
    if head == nil {
        return nil
    }
    //区间[a, b)包含k个待反转元素
    a := head
    b := head
    for i := 0; i < k; i++ {
        //base case,不足k个,不需要反转
        if b == nil {
            return head
        }
        b = b.Next
    }
    //反转前k个元素
    newHead := reverse(a, b)
    a.Next = reverseKGroup(b, k)
    return newHead
}

//反转a到b之间的节点
func reverse(a *ListNode, b *ListNode) *ListNode {
    var prev *ListNode = nil
    curr := a
    for curr != b {
        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;
        }
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode) {
    //反转链表 + 找链表中间节点 + 交叉合并两个链表
    
    if head == nil {
        return
    }
    mid := midNode(head)
    L1 := head
    L2 := mid.Next
    mid.Next = nil
    L2 = reveNode(L2)
    
    mergeNode(L1, L2)
}

//反转单链表
func reveNode(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var pre *ListNode = nil
    cur := head
    for cur != nil {
        nxt := cur.Next
        cur.Next = pre
        pre = cur
        cur = nxt
    }
    return pre
}

//找链表中间节点
func midNode(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

//交叉合并两个链表
func mergeNode(a *ListNode, b *ListNode) {
    var temp_a *ListNode
    var temp_b *ListNode
    for a != nil && b != nil {
        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;
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    //思路：归并排序

    //base case 
    if head == nil || head.Next == nil {
        return head
    }

    //快慢指针，找到链表中间节点，从中间节点一分为二
    slow := head
    fast := head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    //切链
    fast = slow.Next
    slow.Next = nil

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

//合并两个链表
func merge(a *ListNode, b *ListNode) *ListNode {
    dummy := &ListNode{Val: -1}
    p := dummy
    for a != nil && b != nil {
        if a.Val < b.Val {
            p.Next = a
            a = a.Next
        } else {
            p.Next = b
            b = b.Next
        }
        p = p.Next
    }

    if a != nil {
        p.Next = a
    }
    if b != nil {
        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;
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    //思路：找到链表的中间节点，反转链表的后半部分，和前半部分一一对比
    if head == nil {
        return true
    }

    //找到链表中间节点
    Mide := midListNode(head)

    //反转后半部分
    temp := reveListNode(Mide)

    p := head
    q := temp
    for q != nil {
        if p.Val != q.Val {
            return false
        }
        p = p.Next
        q = q.Next
    }
    return true
}

//反转链表
func reveListNode(head *ListNode) *ListNode {
    var pre *ListNode = nil
    cur := head
    for cur != nil {
        nxt := cur.Next
        cur.Next = pre
        pre = cur
        cur = nxt
    }
    return pre
}

//寻找链表中间节点
func midListNode(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast != nil && fast.Next != nil {
        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;
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || k == 0 {
        return head
    }
    n := 1       //链表的长度
    cur := head  //尾节点
    for cur.Next != nil {
        cur = cur.Next
        n++
    }
    k = k % n
    p := head
    
    for i := 0; i < n-k-1; i++ { //找到链表的第 n-k 个节点
        p = p.Next
    }

    // 拼接
    cur.Next = head
    head = p.Next //新的头节点
    p.Next = nil  //断开

    return head
}