Reverse Nodes in k-Group

發表於   |   分類於

LeetCode: Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

不知为何会将这道题目设置为Hard……

解题的主要思路是：

  • 将原来的链表分割为若干块，记录下每一块的起始节点与终结节点；
  • 将每一小段逆置；
  • 将逆置后的段落拼接起来；

AC代码：

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

#include <vector>
using namespace std;

class Solution {
public:

    struct ListPair
    {
        ListNode* head;
        ListNode* tail;
        int nums; // 有多少节点
        ListPair()
        {
            head = NULL;
            tail = NULL;
        }
    };

    vector<ListPair> pairs;

    void reverse(ListNode* head, ListNode* tail, ListNode** nhead, ListNode** ntail)
    {
        ListNode* th = head;
        ListNode* tt = tail->next;
        ListNode* h = NULL;
        ListNode* t = head;
        while (head != tt)
        {
            t = head;
            head = head->next;
            t->next = h;
            h = t;
        }
        *nhead = tail;
        *ntail = th;
    }

    ListNode* reverseKGroup(ListNode* head, int k)
    {
        if (head == NULL)
        {
            return NULL;
        }
        else if (head->next == NULL)
        {
            return head;
        }
      	int i = 0;
        ListPair lpair;

        while (head) // 切分链表
        {
            i++;
            if (head->next == NULL)
            {
                lpair.tail = head;
                lpair.nums = i;
                i = 0;
                pairs.push_back(lpair);
                lpair.head = NULL;
                lpair.tail = NULL;
                lpair.nums = 0;
            }
            else
            {
                if (i == 1)
                {
                    lpair.head = head;
                }
                else if (i == k)
                {
                    lpair.tail = head;
                    lpair.nums = k;
                    i = 0;
                    pairs.push_back(lpair);
                    lpair.head = NULL;
                    lpair.tail = NULL;
                    lpair.nums = 0;
                }
            }
            lpair.nums = i;
            head = head->next;
        }

        for (int i = 0; i < pairs.size(); ++i) // 逆置每一段
        {
            if (pairs[i].nums == k)
            {
                reverse(pairs[i].head, pairs[i].tail, &pairs[i].head, &pairs[i].tail);
            }
        }

        for (int i = 0; i < pairs.size() - 1; ++i) // 重新连接
        {
            pairs[i].tail->next = (pairs[i + 1].head==NULL)?(pairs[i + 1].tail):(pairs[i + 1].head);
        }

        return pairs[0].head;
    }
};