NC2 重排链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        
        // 注意点 : "原地算法" 的概念自行了解
        
        // 关键:
        // 利用递归计算链表长度
        // 利用回溯记录当前节点的位置
        
        curNode = head;
        recursion(curNode);
    }
    
private:
    void recursion(ListNode *node)
    {
        if (node == nullptr) return;
        listLen++;
        curNodeNum++;
        recursion(node->next);
        curNodeNum--;
        
        if (listLen - curNodeNum < (listLen+1)/2)
        {
            ListNode* tmpNode = curNode;
            curNode = curNode->next;
            tmpNode->next = node;
            node->next = curNode;
        }
        
        // 中间的 node 需要特殊处理
        // Hint : 奇偶的情况是不同滴，这里可以优化一下
        if (curNodeNum == (listLen + 1)/2)
        {
            listLen%2 == 1 ? node->next = nullptr : node->next->next = nullptr;
        }  
    };
    
private:
    uint64_t listLen = 0;            // 链表的长度
    uint64_t curNodeNum = 1;         // 当前递归函数处理的节点所在的位置
    ListNode* curNode = nullptr;     // 当前处理的节点
};



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