Catch Your Dream

0%

LeetCode-025-Reverse Nodes in k-Group

Posted on Edited on In Disqus:
Symbols count in article: 3.2k Reading time ≈ 8 mins.

Problem

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

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Examples:

Input: 1-2-3-4-5
Output:

k=2, 2-1-4-3-5
k=3, 3-2-1-4-5

Solutions

  • 递归, 每次改变k个节点的链接顺序, 然后令最后一个节点的next等于下一次递归的返回值, 最后返回头节点, 如果本次不满k个, 直接返回. 每次递归的内容可以是迭代或者用栈, 两种方式的时间差不多
  • 迭代, 基于第24题的迭代, 每次修改完一段之后, 要将此段和前一段相连, 还要和后一段相连, 要注意很多细节
  • 利用栈, 因为k个节点进栈顺序和出栈顺序正好相反

C++ Codes

节点数据结构

1
2
3
4
5
6
7
8
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

递归+栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1 || head==NULL) return head;
        ListNode* stack[k];
        ListNode *p=head;
        //存入栈中
        for(int i=0;i<k;i++){
            if(p==NULL)return head;
            stack[i]=p;
            p=p->next;
        }
        //逆序
        for(int i=k-1;i>0;i--){
            stack[i]->next=stack[i-1];
        }
        //和后一段相连
        stack[0]->next=reverseKGroup(p, k);
        //每次递归返回头节点
        return stack[k-1]; 
    }
};

纯迭代, 相对递归感觉比较麻烦, 逻辑上要想更多, 但是资源肯定比递归消耗少

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
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1) return head;
        ListNode *front, *rear, *tmp, *p, *q, *s;
        front=head;
        for(int i=0;i<k;i++){
            if(front!=NULL) front=front->next;
            else return head;
        }
        front=rear=head;
        //front指向第一个节点, rear指向k+1个节点
        for(int i=0;i<k;i++){
            if(i==k-1) head=rear;
            rear=rear->next;
        }
        
        //pre是前一段最后一个节点
        ListNode *pre=new ListNode(0);
        while(true){
            p=front;q=front->next;s=q->next;
            while(q!=rear){
                q->next=p;
                p=q;q=s;
                //这里要注意rear可能是NULL, s->next需判断
                if(s==rear && s==NULL) break;
                else s=s->next;                
            }
            //本段和后一段相连,此时q=rear, s=rear->next, 
            front->next=rear;
            //前面一段和本段第一个节点相连 
            pre->next=p;
            pre=front;
            //更新front和rear
            front=rear;
            for(int i=0;i<k;i++) {
                //rear可能没到目标就成了NULL
                if(rear==NULL)return head;
                rear=rear->next;
            }
        }
        return head;  
    }
};

Python Codes

递归+栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if k==1 or head==None:
            return head
        stack=[]
        p=head;
        #存入栈中
        for i in range(k):
            if p==None:
                return head
            stack.append(p);
            p=p.next
        
        #逆序
        for i in range(k-1, 0, -1):
            stack[i].next=stack[i-1]
        #和后一段相连, python递归要self.reverseKGroup()
        stack[0].next=self.reverseKGroup(p, k)
        #每次递归返回头节点
        return stack[k-1]

迭代

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if k==1:
            return head
        front=head
        for i in range(k):
            if front!=None:
                front=front.next
            else:
              return head    
        
        front=rear=head
        #front指向第一个节点, rear指向k+1个节点
        for i in range(k):
            if i==k-1:
                head=rear
            rear=rear.next 
            
        #pre是前一段最后一个节点
        pre=ListNode(0);
        while True:
            p=front
            q=front.next
            s=q.next
            while q!=rear:
                q.next=p
                p=q
                q=s
                #这里要注意rear可能是NULL, s->next需判断
                if s==rear and s==None:
                    break
                else:
                    s=s.next                     
            #本段和后一段相连,此时q=rear, s=rear->next, 
            front.next=rear
            #前面一段和本段第一个节点相连 
            pre.next=p
            pre=front
            #新front和rear
            front=rear;
            for i in range(k):
                #rear可能没到目标就成了NULL
                if rear==None:
                    return head
                rear=rear.next
        return head;

总结

  • 逆序问题可利用栈的特性
  • 发现问题可以分为多个子问题, 利用递归
  • 迭代的过程注意避免空指针和环

Python是真的不太熟悉啦

disqus gitalk