leetcode_reverse_nodes_in_k_group

发表于

难度：Hard

解题思路：是翻转两个节点链表的延伸。在纸上画图！找出翻转k个节点的链表的方法。

代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // if(head==NULL)  return NULL;
        ListNode* dummy = new ListNode(-1), *cur = dummy;
        dummy->next = head;
        while(cur != NULL)
        {
            ListNode* first = cur->next, *second = cur;
            int i = 0;
            for(; i < k; i++)
            {
                if(second->next != NULL)
                {
                    second = second->next;
                }
                else
                {
                    break;
                }
            }
            if(i != k)
                break;
            ListNode* change_node = first;
            ListNode* change_node_pre = second->next;
            cur->next = second;
            for(int j = 0; j < k; j++)	//这里用k来判断会方便减少麻烦
            {
                // cout<<"value:"<<change_node->val<<endl;
                ListNode* change_node_next = change_node->next;
                change_node->next = change_node_pre;
                change_node_pre = change_node;
                change_node = change_node_next;               
            }
            cur = first;
        }
        return dummy->next;
    }
};

运行结果：22ms，超过43.06%