LeetCode 143. 重排链表 （快慢指针、反转链表、合并链表）_链表重排快慢指针

143. 重排链表
这题算是把三个easy题并一块了。

/**
 * 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;
        // 找出中点
        int len = 0, halflen;
        ListNode* cur = head;
        while(cur){
            len++;
            cur = cur->next;
        }
        halflen = len/2;
        int pos = halflen + (len%2);
        
        // 反转后半部的链表
        cur = head;
        ListNode* pre = nullptr;
        for(int i=0;i<pos;i++){
            pre = cur;
            cur =  cur->next;
        }

        pre->next = nullptr;
        ListNode *another_head = reverseList(cur);
        // 合并两个链表
        mergeTwoList(head,another_head);
    }

    // 链表的头插法反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode *newHead = nullptr,*nxt;
        while(head){
            nxt = head->next;
            head->next = newHead;
            newHead = head;
            head = nxt;
        }
        return newHead;
    }

    // 双指针合并两个链表
    void mergeTwoList(ListNode *h1,ListNode *h2){
        ListNode *header = new ListNode , *cur = header;
        while(h1 && h2){
            ListNode* h_1 = h1->next , *h_2 = h2->next;
            h1->next = h2;
            cur->next = h1;
            cur = h2;
            h1 = h_1;
            h2 = h_2;
        }
        if(h1) cur->next = h1;
        if(h2) cur->next = h2;
        delete header;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66