题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

题意概述

给定一个链表
要求将链表中的节点每k个一组翻转
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样

方法一：递归

思路与具体做法

思路：
- 用递归实现不断分割链表，并对分割后的子链表进行反转，反转后再拼接回去即可
具体实现：
- 用到了四个指针，p2,p3指向当前反转区间的首尾结点，p1指向当前反转区间的首结点的前驱，p4指向当前反转区间的尾结点的后继
- 每次对分割后的反转区间链表建立伪头结点，p1指向这个伪头结点，p2指向传来的头结点，p3初始指向伪头结点然后先行k步即指向第k个结点，p4指向p3的后继即可
- 然后在p1,p3后断开后继，反转这段子链表拼接回去即可
- 对于剩下的不满k个结点的子链表直接返回即可

class Solution{
public:
    void reverse(ListNode* head){//反转链表
        ListNode* p=head,*pre=NULL,*next=p->next;
        while(p){
            p->next=pre;//反转next指针
            pre=p;
            p=next;
            next=p->next;
        }
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL)return head;
        ListNode* head2=new ListNode(0);//伪头结点 
        head2->next=head;
        ListNode* p1=head2,*p2=head,*p3=p1,*p4;//p2,p3指向当前反转区间的首尾结点，p1指向当前反转区间的首结点的前驱，p4指向当前反转区间的尾结点的后继 
        for(int i=0;i<k;i++){//p3指向第n个结点 
        	if(p3->next)p3=p3->next;//p3不断回退到最后一个结点 
            else return head;//未遍历完k个结点则返回剩余链表 
		}
		p4=p3->next; 
		p3->next=NULL;//截取子链表
		p1->next=NULL;
		reverse(p2);//反转子链表
		p1->next=p3;//合并回原先的链表
		p2->next=reverseKGroup(p4,k); 
		return head2->next;//返回结果链表 
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O (n)$ ，遍历了长度为n的链表，next指针在 $O (n / k)$ 个结点分割子链表，每次分割后进行一次 $O (k)$ 的反转操作
空间复杂度： $O (n)$ ，最坏情况下的递归栈深度是 $O (n)$

方法二：栈

思路与具体做法

遍历原链表，并在遍历过程中不断将结点权值压入栈
每当栈满k个元素，就将栈内元素全部出栈用以新建链表
最后当栈s还有剩余，即链表结点不能被k整除时，将剩下的元素入两次栈，即可实现原顺序的结点权值

class Solution{
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL)return head;
        ListNode* head2=new ListNode(0);//新建链表 
        ListNode* p=head2;//p是头指针 
        stack<int>s,s2; 
        while(head){//遍历旧链表 
        	s.push(head->val);//权值压入栈 
        	if(s.size()==k){//当栈满k个元素，就将栈内元素全部出栈用以新建链表 
        		while(!s.empty()){
        			p->next=new ListNode(s.top());s.pop();//新建链表 
        			p=p->next;//指针后移 
				}
			}
        	head=head->next;//指针后移 
		} 
		while(!s.empty()){//当栈s还有剩余，即链表结点不能被k整除时，将剩下的元素入两次栈，即可实现原顺序的结点权值  
			s2.push(s.top());s.pop();
		}		
		while(!s2.empty()){
			p->next=new ListNode(s2.top());s2.pop();//新建链表 
            p=p->next;//指针后移 
		}		
		return head2->next;//返回结果链表 
    }
};