LeetCode 25.k个一组翻转链表(Reverse Nodes in k-Group)

LeetCode.jpg

 

k个一组翻转链表

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

切题

一、Clarification

1、每组k个元素翻转后，每组之间的衔接。[1,k] 与 [k+1,2k]之间衔接

2、注意 剩余元素的处理

二、Possible Solution

1、迭代

遍历链表 找出每组的 首尾以及下一组的首，借助单链表翻转获得翻转后的首尾，对首尾节点衔接处理，对哨兵节点移位处理

时间复杂度 O(N)

2、递归

递归终止条件：

剩余节点 < k

递归从里向外出来，每层递归返回当前层级链表翻转后的头节点，那么每层递归中我们知道当前层级翻转后的头尾节点以及下一个k元素组的头节点（递归的上一层级），可以很轻松地将翻转后的链表衔接起来

3、借助栈

将k个元素压入栈，通过出栈翻转，注意剩余元素处理

Python3实现

迭代 借助单链表翻转

# @author:leacoder
# @des: 迭代 借助单链表翻转  k个一组翻转链表
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        cur = head #由于遍历
        dim = ListNode(0) #新建一节点 
        dim.next = head #next指向head
        pre = dim #pre 赋值为 dim  1、记录和获取 k个一组的头 2、方便统一处理
        # pre 与 dim 均为哨兵
        count = 1
        while cur: #遍历链表
            if count % k == 0: #k个一组 对这里面的数据翻转
                nextstart = cur.next #记录 后一个 k个一组的 头节点
                cur.next = None #赋值为None 前面 k个一组数据 为新的链表 以 None结束 这个新链表可以采用206的处理方式
                end, start = self.reverse(pre.next)  #翻转新链表 返回翻转的  尾 和 头  注pre.next 为新链表翻转前的头
                # 衔接处理，哨兵的next指向翻转后的头， 翻转后的尾的next指向nextstart
                # pre 和 cur 依次下移k个元素 变为 end 和 nextstart下一轮处理就变成本轮一样了
                pre.next,end.next,pre,cur = start,nextstart,end,nextstart
            else:
                cur = cur.next #我们关心k个一组的首尾
            count += 1
        return dim.next
    
    def reverse(self, head): #翻转链表
        dim1,cur,pre = head,head,None
        while cur: #遍历
            cur.next,pre,cur  = pre,cur,cur.next
        return dim1,pre    #翻转后end 和 start

递归

# @author:leacoder
# @des: 递归  k个一组翻转链表
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
       
        if self.isEnd(head,k):
            return head
        pre = ListNode(None) # 哨兵
        pre.next,cur,count =  head,head,1  
 
        while count <= k: # 翻转 k个元素链表  处理类似 206
            cur.next,pre,cur,count  = pre,cur,cur.next,count + 1 
        # 循环结束后 cur 指向 下一组 k个元素(未翻转)的头 ;pre指向当前组在翻转后的头节点
        nexthead = self.reverseKGroup(cur,k) # nexthead 下一组翻转后的头节点
 
        head.next = nexthead #当前组的head在翻转后成为尾节点，其next指向nexthead 下一组翻转后的头节点
        return pre  # 返回 翻转后的头节点
 
    # 递归终止判断：
    def isEnd(self,head,k):
        count,cur = 0,head
        while cur:
            count = count + 1
            cur = cur.next
            if count >= k:
                return False # 
        return True

借助栈

 
# @author:leacoder
# @des: 借助栈  k个一组翻转链表
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        result= ListNode(None)
        cur,result.next = head,head
        tmpresult = result
        stack = [] # 列表实现栈的 先入后出功能
        count = 0
 
        while cur:
            count = count + 1
            stack.append(cur) # 入栈
            cur = cur.next
            if count % k == 0: # 已存储k个元素
                count = 0
                while stack: # 出栈倒换
                    tmpresult.next = stack.pop()
                    tmpresult = tmpresult.next
 
        # 处理 stack 中剩余元素
        while stack:
            tmpresult.next = stack.pop(0) # 
            tmpresult = tmpresult.next 
        return result.next

C++实现

存储法

用数组存储k个元素，虽然能通过但是执行用时有点长，不过逻辑简单

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * @author:leacoder
 * @des: 存储法 k个一组翻转链表
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *nodearray[k];//存储 需翻转的 k个节点
        ListNode* result = new ListNode(0); //翻转后链表 用于结果返回
        ListNode* ret = result;//由于存储翻转后链表
        int count = 0;
        while( NULL != head){
            ListNode* next = head->next; //记录下移节点
            nodearray[count] = head; //记录到数组
            count++;//数组 下标自加 
            if(k == count){ //已存 k个值  需要翻转了
               for(int i = k;i>0;i--){ //循环读取 数组中数据
                   ret->next = nodearray[i-1]; //从后往前去数组中数据 添加到ret链表中
                   ret = ret->next;//移位
                   nodearray[i-1] = NULL;//置空
                   count--;//数组中数据个数--
               }
            }
            head = next;
        }
        
        for(int i = 0;i<count;i++){//处理不需要翻转的数据
           ret->next = nodearray[i];
           ret = ret->next;
           nodearray[i] = NULL;
        }
        ret->next = NULL;
        return result->next;
    }
};

k作为函数参数传入后就确定了可以当做常数，但是k作为参数可以为合理范围内任意值不确定，这点和题目描述说明貌似有点出入
说明 : 你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

我这种方法处理也只是提供一种思路，待后续其他实现方法

---

GitHub链接：
https://github.com/lichangke/LeetCode

知乎个人首页：
https://www.zhihu.com/people/lichangke/

简书个人首页：
https://www.jianshu.com/u/3e95c7555dc7

个人Blog:
https://lichangke.github.io/

欢迎大家来一起交流学习