如何 K 个一组反转链表 :: labuladong的算法小抄

[labuladong]

文章链接点这里：如何 K 个一组反转链表

评论礼仪 见这里，违者直接拉黑。

[jswxwxf]

js 版

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

function buildLinkList(values) {
  return values.reverse().reduce((acc, val) => new ListNode(val, acc), null);
}

// ---- Generate our linked list ----
const linkedList = buildLinkList([1, 2, 3, 4, 5, 6]);

let count = 0;
function log(n, message, obj = null) {
  if (typeof obj === "object" && obj !== null) {
    obj = JSON.stringify(obj);
  }
  console.log(new Array(n < 0 ? 0 : n).fill(" ").join(""), message, obj);
}

var reverseKGroup = function (head, k) {
  if (head === null) return null;

  let a = head,
    b = head;

  // 区间 [a, b) 包含 k 个待反转元素
  for (let i = 0; i < k; i++) {
    // 不足 k 个，不需要反转，base case
    if (b === null) return head;
    b = b.next;
  }

  // 反转前 k 个元素
  const newHead = reverse(a, b);

  // 递归反转后续链表并连接起来
  a.next = reverseKGroup(b, k);

  return newHead;

  function reverse(a, b) {
    let prev = null,
      cur = a,
      next = a;
    while (cur !== b) {
      next = cur.next;
      // 逐个结点反转
      cur.next = prev;
      // 更新指针位置
      prev = cur;
      cur = next;
    }
    // 返回反转后的头结点
    return prev;
  }
};

console.log(JSON.stringify(reverseKGroup(linkedList, 2), null, 2));

[Bittttter]

reverse 的声明可以放在 reverseKGroup 外部避免每次递归的时候重新定义函数

[mmungdong]

golang

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil {
        return head
    }
    a, b := head, head
    for i := 0; i < k; i++ {
        if b == nil {
            return head
        }
        b = b.Next
    }
    newHead := reverse(a, b)
    a.Next = reverseKGroup(b, k)
    return newHead
}

func reverse(a, b *ListNode) *ListNode {
    var pre,cur,next *ListNode = nil,a,a
    for cur != b {
        next = cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

[shaopu1225]

自己的解法， C++

    ListNode* reverseKGroup(ListNode* head, int k) {
        // base case, don't need to reverse
        if (head == nullptr || head->next == nullptr) return head;
        
        // successor stores the next sub-linked list head
        ListNode* successor = nullptr;
        // nidicate whether we meet a end-fragment-cut situation
        bool end = false;
        
        // reverse the Nst K nodes, and return the current head 
        // whether reverse or not when meeting the end <k elements, so it might be the current head, or current tail
        ListNode* reverseFirst = reverseBetween(head, k, successor, end);
        
        // recursion on sub-list starting at successor, excluding the K nodes before
        ListNode* reverseNextKGroup = reverseKGroup(successor, k);
        
        // connect the past reversed fragment to the next reversed fragment when not end-fragment-cut
        if (!end)
            head->next = reverseNextKGroup;             
        
        // for the end fragment, we don't need to connect anything    
        
        return reverseFirst;
    }
    
    
    // a helper function, reversing between node left & node left + k - 1
    // give a successor argument, so that we can use the successor as the next start point
    ListNode* reverseBetween(ListNode* left, int k, ListNode*& successor, bool& end) {
        // base case 1
        if (k == 1) {
            successor = left->next;
            return left;
        }
        // base case 2: end-fragment-cut situation, less than K elements:
        if (left== nullptr || left->next == nullptr) {
            // notify all reverseBetween() functions that "LOL, I MEET THE END AND GOT CUT BEFORE FINISHING K TRAVERSAL!"
            end = true;
            return left;
        }
        
        //recursion
        ListNode* reverseFromNext = reverseBetween(left->next, k - 1, successor, end);
        // only if `end` is false, we do the following
        if (!end) {
            left->next->next = left;
            left->next = successor;   
            return reverseFromNext; 
        }
        // end-fragment-cut situation
        else
            // NOTICE: return the current head of the end fragment rather than the current tail of the end fragment
            return left;
    }

[cdongting]

c语言版本

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseN(struct ListNode* left,struct ListNode* right)
{
    if(left->next == right)
    {
        return left;
    }
    struct ListNode* return_node = reverseN(left->next, right);
    left->next->next = left;
    left->next = NULL;
    return return_node;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode *left, *right;
    left=right=head;
    for(int i =0; i<k; i++)
    {
        if(!right)
            return head;
        right = right -> next;
    }
    struct ListNode *newhead = reverseN(left,right);
    left->next = reverseKGroup(right,k);
    return newhead;
}

[clearlovel7]

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseK(self,a,b):
        pre,cur=None,a
        while cur!=b:
            nxt=cur.next
            cur.next=pre
            pre=cur
            cur=nxt
        return pre

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head==None:
            return None
        a,b=head,head
        for i in range(k):
            if b==None:
                return head
            b=b.next
        newhead=self.reverseK(a,b)
        a.next=self.reverseKGroup(b,k)
        return newhead

[fornobugworld]

所以这道题是不是有外递归迭代，内递归迭代，共四钟组合解法。。。

[codingwjp]

好牛蛙

[1302304703]

好厉害，我要看好一会才能理解，大佬！

[Days-Go-By]

用前面得小结得递归

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        ListNode p1 = head;
        int count = 0;
        while(p1 != null){
            count++;
            p1 = p1.next;
        }
        ListNode newNode = head;
        for(int i = 1; (i+k-1) <= count; i+=k){
            newNode = reverseK(newNode,i,i+k-1);
        }
        return newNode;
    }

    // 反转链表中得区间节点
    public ListNode reverseK(ListNode head, int m, int n){
        if(m == 1){
            return reverseN(head,n);
        }
        head.next = reverseK(head.next, m - 1, n -1);
        return head;
    }
    // 反转链表中得前n个节点
    ListNode successor = null;
    public ListNode reverseN(ListNode head, int n){
        if(n == 1){
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n -1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}

[creanLiu]

结合前一章

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode helper = head;
        for(int i = 0; i < k; i++){
            if(helper == null){
                return head;
            }
            helper = helper.next;
        }
        ListNode newHead = reversN(head, k);
        head.next = reverseKGroup(bridge,k);
        return newHead;
    }
    ListNode bridge = null;
    public ListNode reversN(ListNode head, int k){
        if(k == 1){
            bridge = head.next;
            return head;
        }
        ListNode last = reversN(head.next, --k);
        head.next.next = head;
        head.next = bridge;
        return last;
    }
}

[sayicheng]

class Solution:
    def __init__(self):
        successor = None

    def reverseN(self, head: ListNode, n: int) -> ListNode:
        if (n == 1):
            self.successor = head.next
            return head

        last = self.reverseN(head.next, n - 1)
        head.next.next = head
        head.next = self.successor
        return last

    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if left == 1:
            return self.reverseN(head, right)
        
        head.next = self.reverseBetween(head.next, left-1, right-1)
        return head

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: 
        n = 0
        p = head
        while p:
            p = p.next
            n += 1

        count = n // k
        for i in range(0, count):
            left = i*k + 1
            right = i*k + k
            head = self.reverseBetween(head, left, right)        
        return head

[baoyun-chen]

纯递归解法

public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        int length = 0;
        ListNode node = head;
        while(node != null){
            length++;
            node = node.next;
        }

        int round = length/ k;
        ListNode pre = new ListNode();
        ListNode newHeadPre = new ListNode();
        pre.next = head;
        node = head;

        for( int r = 1; r <= round; r++){
            ListNode next;
            ListNode previous = null;
            for(int i = 1;  i <=k ; i++){
                next = node.next;
                node.next = previous;

                previous = node;
                node = next;
            }
            if(r == 1){
                newHeadPre.next = previous;
            }
            ListNode thisLast = pre.next;
            thisLast.next = node;
            pre.next = previous;
            pre = thisLast;
        }

        return newHeadPre.next;
    }

[ThiriKid]

你这是纯迭代吧

[wann-he]

反转a，b的节点那块的代码是不是应该把 pre初始指向b

[Goolloo]

Java Double Iterations

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyHead = new ListNode(-1, head);
        
        ListNode previousNode;
        ListNode oldHeadNode = dummyHead;
        ListNode reversedHeadNode = null;
        while(oldHeadNode != reversedHeadNode) {
            previousNode = oldHeadNode;
            oldHeadNode = oldHeadNode.next;
            
            reversedHeadNode = reverseFirstK(oldHeadNode, k);
            previousNode.next = reversedHeadNode;
        }
        
        return dummyHead.next;
    }
    
    /*
    *  return new head.
    */
    private ListNode reverseFirstK(ListNode head, int k) {
        ListNode node = head;
        // check if has k nodes
        for(int i = 0; i < k; i++) {
            if(node == null) {
                // if less than k, return old head as new head, so no reverse
                return head;
            }
            node = node.next;
        }
        
        // reset and start reversing
        ListNode lastNode = node; // the k+1 node
        node = head;
        ListNode nextNode = null;
                
        for(int i = 0; i < k; i++) {
            nextNode = node.next;
            node.next = lastNode;
            
            lastNode = node;
            node = nextNode;
        }
                
        return lastNode;
    }
}

[LebronHarden1]

牛牛牛

[lzwanan]

打卡打卡

[zbf1-999]

纯递归解法，用for循环配合temp指针用来确定不会超出范围

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //1.反转前k个 然后从最后一个反转的后一位节点开始反转前k个  直到不足k个
        ListNode temp=head;
        for(int i=0;i<k;i++){
            if(temp==null){
                return head; 
            }
            temp=temp.next;
        }
        ListNode newHead=reverseN(head,k);
        head.next=reverseKGroup(temp,k);
        return newHead;
    }



    ListNode successor=null;
    //反转前n个
    public ListNode reverseN(ListNode head,int n){
        if(n==1){
            //此时为需要反转的最后一位，next就是不需要反转的首位
             successor=head.next;
            return head;
        }

        //递归反转后n-1个，再把第一个接在最后  返回值为 反转后的新头节点
        ListNode last=reverseN(head.next,n-1);
        head.next.next=head;
        head.next=successor;
        return last;
    }
}

[RAZELXZ]

使用前文递归解法：

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode a = head, b = head;
        for (int i = 0; i < k; i++) {
            if (b == null) return head;
            b = b.next;
        }
        ListNode newHead = reverseN(a, k);
        a.next = reverseKGroup(b, k);
        return newHead;
    }
ListNode successor = null;
public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode Last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return Last;
    }

[Quanticco]

reverse函数部分可以利用Python的多元赋值优化以下

def reverseN(self, a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
        p, pre = a, None
        while p != b:
            p, pre, pre.next = p.next, p, pre
        return pre

[CarlLy7]

打卡，附上详细的Java注释代码

    //使用迭代的方法实现反转一个区间的链表的功能
    //这里就是反转[a,b)这个区间的节点
    private ListNode reverseRange(ListNode a, ListNode b) {
        //定义前驱、当前、后继节点指针
        ListNode pre, cur, next;
        pre = null;
        cur = next = a;
        while (cur != b) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //因为是左闭右开区间，所以最后返回的是pre而不是cur
        return pre;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1 || head == null) {
            return head;
        }
        ListNode a, b;
        a = b = head;
        //这个循环就是去让指针往后移动我们要反转的个数来实现反转区间
        for (int i = 0; i < k; i++) {
            //如果最后不够k个节点了，就不反转了，直接结束
            if(b==null){
                return head;
            }
            b=b.next;
        }
        //最前面的这个反转后的新的头节点就是我们最后要返回的节点
        ListNode newHead = reverseRange(a, b);
        //反转之前的第一个节点变成了最后一个节点要和下一组反转的头节点连接起来
        a.next=reverseKGroup(b,k);
        return newHead;
    }

[niuqitong]

调用了上篇教程的 翻转前k个元素 这个函数

var after *ListNode
func reverseFirstN(head *ListNode, n int) *ListNode {
	if n == 1 {
		after = head.Next
		return head
	}
	last := reverseFirstN(head.Next, n-1)
	head.Next.Next = head
	head.Next = after
	return last
}
func reverseKGroup(head *ListNode, k int) *ListNode { // 25. k个一组翻转链表
	l, r := head, head
	prev := &ListNode{Val: -1}
	cur := prev
	cnt := 0
	for r != nil {
		cnt++
        nxt := r.Next
		if cnt == k {
			cur.Next = reverseFirstN(l, k)
			cur = l
			l = nxt
            cnt = 0
		}
		r = nxt
	}
	return prev.Next
}

[yihang-gao]

python 版本， 用前面学的递归翻转前k个元素的递归

class Solution:
def init(self):
self.successor = None

def reverseTopK(self, head: ListNode, k: int) -> Optional:
    if not head:
        return head

    if k == 1:
        last = head
        self.successor = head.next
        return last


    last = self.reverseTopK(head.next, k-1)

    head.next.next = head
    head.next = self.successor
    

    return last


def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

    p = head

    if not head:
        return head

    for i in range(k-1):
        p = p.next
        if not p:
            return head

    last = self.reverseTopK(head, k)

    last_sub = self.reverseKGroup(self.successor, k)

    head.next = last_sub

    return last

Console

[yexia553]

打卡，认真看了一遍，还没真正做题

[EchooWww]

在上一篇文章reverseN的基础上改写了一下

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode a = head;
        ListNode b = head;
        // move our pointers iteratively, to guarantee b is k steps ahead of a
        for(int i = 0; i< k; i++) {
            if(b == null) return head;
            b = b.next;
        }
        // create our new head node by reversing the first group of k
        ListNode newHead = reverseN(a, k);
        // recursively call reverseKGroup to start from b, and connect it to the last node reversed in last round
        a.next = reverseKGroup(b, k);
        return newHead;
    }

    //Initialize successor to null
    ListNode successor = null;
    public ListNode reverseN(ListNode head, int n) {
        // Find the real successor in our base case
        if(n==1) {
            successor = head.next;
            return head;
        }
        // recursively call reverseN by shifting it to the next node 
        ListNode last = reverseN(head.next, n-1);
        // Connect the head to our reversed part
        head.next.next = head;
        head.next = successor;
        // return the new head node (which we call last)
        return last;
    }
}

[anglelikepupu]

还不是很清楚

[NokiaX300]

Python版
内层替换为上节的递归

from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None
        a, b = head, head
        for i in range(k):
            if not b:
                return head
            b = b.next
        new_head = self.reverse(a, b)
        a.next = self.reverseKGroup(b, k)
        return new_head

    def reverse(self, a: ListNode, b: ListNode) -> ListNode:
        if a.next == b:
            return a
        last = self.reverse(a.next, b)
        a.next.next = a
        a.next = None
        return last

[KSroido]

2023 柠檬微趣 笔试真题

[BobbyWucj]

C++最佳实现。简洁易懂

class Solution {
    // 反转链表前 N 个节点
    ListNode *reverseN(ListNode *head, int n) {
        if (n == 1)
            return head;

        ListNode *last = reverseN(head->next, n-1);
        // 注意这里需要定义一个临时变量
        ListNode *headNext = head->next;
        head->next = headNext->next;
        headNext->next = head;
        return last;
    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k <= 1)
            return head;

        ListNode *node = head;
        for (int i = 0; i < k-1; ++i) { // 找到第K个节点，也就是第一个分组的最后一个节点
            if (node && node->next)
                node = node->next;
            else // 不足K个，保持原有顺序，直接返回
                return head;
        }
        node->next = reverseKGroup(node->next, k); // 第K+1个节点后面的链表已完成K个一组反转，拼接即可
        return reverseN(head, k); // 反转链表前K个节点
    }
};

[SkyeKD]

可以借鉴92题中的reverseN(ListNode head,int n)函数，翻转链表的前N个元素。
Java版

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode p = head;
        for(int i=0;i<k-1;++i){
            if(p.next==null)return head;
            p = p.next;
        }
        //注意
        if(p.next!=null){
            p.next = reverseKGroup(p.next,k);
        }
        head = reverseN(head,k);
        return head;

    }
    ListNode successor = null;
    public ListNode reverseN(ListNode head,int n){
        if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }
}

[ImZzBy]

题外话：太难了终于登上来了。

我觉得可以沿用东哥92题的递归思想。

92题的函数签名是ListNode reverseBetween(ListNode head, int m, int n)，对于本题来说，m恒为1，n可以通过计算得出（n = (链表长度/k)*k）。

但是，直接把这个思路套进92题似乎不符合递归函数的设计。于是，我又又又去问了gpt老师，以下是gpt老师的解答和代码，我试过了，可以运行（时间0ms，内存42MB）。

gpt3.5老师：你的想法是正确的，递归函数的设计应该是可以只计算一次m和n，然后在递归过程中利用这一次计算结果进行反转链表操作。这样可以减少不必要的重复计算，提高算法的效率。

以下是一个按照你的想法实现的递归算法示例，用于解决LeetCode 25题-K个一组翻转链表问题：

class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) {
curr = curr.next;
count++;
}
if (count == k) {
curr = reverseKGroup(curr, k);
while (count-- > 0) {
ListNode temp = head.next;
head.next = curr;
curr = head;
head = temp;
}
head = curr;
}
return head;
}
}
在这个递归函数中，我们首先计算并移动指针找到待反转的子链表，然后进行递归操作。在递归函数中，我们对每个子链表进行翻转操作，直至整个链表完成翻转。

希望这个示例可以帮助你更好地理解递归算法的设计和实现。如果有任何问题，欢迎继续讨论。

我觉得这个解法和m，n，没有啥关系，还是每次只反转k个。

[ududu61]

看本文之前，还是用的反转单链表的思路去写，递归反转时多写一个basecase放n==1的basecase前面，发现不足k个结点，直接返回nullptr，然后主循环break出去。

看完发现，递归真是怎么样都能写啊，十分灵活，和上一篇反转单链表的思路又有区别了。

但总感觉对链表用前序递归遍历，和迭代差不太多。迭代性能也更高。

• 我的递归

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head->next==nullptr)return head;
        int cnt=0;
        ListNode *dum=new ListNode(-1),*prev=dum;
        prev->next=head;
        while(prev){
            if(cnt%k==0){
                ListNode *cur_next=reverseNnode(prev->next,k);
                if(cur_next==nullptr)break;
                prev->next=cur_next;
            }
            prev=prev->next;
            ++cnt;
        }
        return dum->next;

    }
private:
    ListNode *successor=nullptr;
    ListNode *reverseNnode(ListNode *beg,int n){
        if(beg==nullptr)return nullptr;
        if(n==1){
            successor=beg->next;
            return beg;
        }
        ListNode *reverseHead=reverseNnode(beg->next,n-1);
        if(reverseHead==nullptr)return nullptr;
        beg->next->next=beg;
        beg->next=successor;
        return reverseHead;
    }
};

• 我的迭代

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head->next==nullptr)return head;
        int cnt=0;
        ListNode *dum=new ListNode(-1),*prev=dum;
        prev->next=head;
        while(prev){
            if(cnt%k==0){
                ListNode *examPrev=prev;
                for(int i=0;i!=k;++i){
                    if(examPrev)examPrev=examPrev->next;
                }
                if(!examPrev)break;
                ListNode *cur=prev->next,*curHead=cur;
                ListNode *succ=cur->next;
                for(int i=0;i!=k-1;++i){
                    ListNode *tmp=succ->next;
                    succ->next=cur;
                    cur=succ;
                    succ=tmp;
                }
                prev->next=cur;
                curHead->next=succ;
            }
            prev=prev->next;
            ++cnt;
        }
        return dum->next;
    }
};

[ududu61]

不对，la哥的效率也很高啊，nb