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
{% endnote %}

Solutions

• 遞歸, 每次改變k個(gè)節(jié)點(diǎn)的鏈接順序, 然后令最后一個(gè)節(jié)點(diǎn)的next等于下一次遞歸的返回值, 最后返回頭節(jié)點(diǎn), 如果本次不滿k個(gè), 直接返回. 每次遞歸的內(nèi)容可以是迭代或者用棧, 兩種方式的時(shí)間差不多
• 迭代, 基于第24題的迭代, 每次修改完一段之后, 要將此段和前一段相連, 還要和后一段相連, 要注意很多細(xì)節(jié)
• 利用棧, 因?yàn)閗個(gè)節(jié)點(diǎn)進(jìn)棧順序和出棧順序正好相反

C++ Codes

節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

/**
 * 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(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);
        //每次遞歸返回頭節(jié)點(diǎn)
        return stack[k-1]; 
    }
};

純迭代, 相對(duì)遞歸感覺比較麻煩, 邏輯上要想更多, 但是資源肯定比遞歸消耗少

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指向第一個(gè)節(jié)點(diǎn), rear指向k+1個(gè)節(jié)點(diǎn)
        for(int i=0;i<k;i++){
            if(i==k-1) head=rear;
            rear=rear->next;
        }
        
        //pre是前一段最后一個(gè)節(jié)點(diǎn)
        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;                
            }
            //本段和后一段相連,此時(shí)q=rear, s=rear->next, 
            front->next=rear;
            //前面一段和本段第一個(gè)節(jié)點(diǎn)相連 
            pre->next=p;
            pre=front;
            //更新front和rear
            front=rear;
            for(int i=0;i<k;i++) {
                //rear可能沒到目標(biāo)就成了NULL
                if(rear==NULL)return head;
                rear=rear->next;
            }
        }
        return head;  
    }
};

Python Codes

遞歸+棧

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)
        #每次遞歸返回頭節(jié)點(diǎn)
        return stack[k-1] 

迭代

# 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指向第一個(gè)節(jié)點(diǎn), rear指向k+1個(gè)節(jié)點(diǎn)
        for i in range(k):
            if i==k-1:
                head=rear
            rear=rear.next 
            
        #pre是前一段最后一個(gè)節(jié)點(diǎn)
        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                     
            #本段和后一段相連,此時(shí)q=rear, s=rear->next, 
            front.next=rear
            #前面一段和本段第一個(gè)節(jié)點(diǎn)相連 
            pre.next=p
            pre=front
            #新front和rear
            front=rear;
            for i in range(k):
                #rear可能沒到目標(biāo)就成了NULL
                if rear==None:
                    return head
                rear=rear.next
        return head;  

總結(jié)

• 逆序問題可利用棧的特性
• 發(fā)現(xiàn)問題可以分為多個(gè)子問題, 利用遞歸
• 迭代的過程注意避免空指針和環(huán)

Python是真的不太熟悉啦