如何 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));

[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;
    }

[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;
    }

[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]

牛牛牛

[Sm1lence]

打卡打卡

[lihuagang03]

打卡，感谢楼主！

[deepbreath373]

打卡

[zhaoedf]

后序遍历，自己控制想要返回的东西

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        next_iter_head = head
        new_head = head
        last_sub_tail = None
        
        i = 1
        while True:
            sub_head, sub_tail, next_iter_head = self.recursion(next_iter_head, k, k)
            # print(sub_head.val, sub_tail.val, next_iter_head.val)
            
            if i == 1:
                new_head = sub_head

            if sub_tail is not None and i > 1:
                last_sub_tail.next = sub_head
            elif sub_tail is None:
                if i > 1:
                    last_sub_tail.next = last_next_iter_head
                else:
                    new_head = head
                break
            
            i += 1
            
            last_sub_tail = sub_tail
            last_next_iter_head = next_iter_head
            
        
        return new_head
    
    def recursion(self, head, k, total_k):
        if head is not None and k == 1:
            return head, None, head.next
        
        if head is None and k >= 1:
            return None, None, None

        sub_head, sub_tail, next_iter_head = self.recursion(head.next, k-1, total_k)
        
        if sub_head is None:
            return None, None, None
        
        head.next.next = head
        head.next = None
        
        if k == total_k:
            sub_tail = head
    
        
        return sub_head, sub_tail, next_iter_head

[Erik-Lin]

二刷！

[lizhi-a]

js，结合前一章，主要使用【反转前 n 个节点】方法

// 反转前 n 个节点
var successor = null
var reverseList = (head, n) => {
  if (n === 1) {
    successor = head.next
    return head
  }
  let last = reverseList(head.next, n - 1)
  head.next.next = head
  head.next = successor
  return last
}
var reverseKGroup = function (head, k) {
  let a = head
  let b = head
  for (let i = 0; i < k; i++) {
    if(b === null) return head
    b = b.next
  }
  let newList = reverseList(head, k)
  a.next = reverseKGroup(b, k)
  return newList
};

[LeeHaruYa]

滴滴滴打卡

[networkcv]

 public ListNode reverseKGroup2(ListNode head, int k) {
            int i = k, j = k;
            ListNode cur = head;
            //找第一组k的节点后边的链表
            while (j-- > 0) {
                // 递归的base case
                if (cur == null) {
                    return head;
                }
                cur = cur.next;
            }
            //分解问题的核心
            ListNode pre = reverseKGroup2(cur, k);
            //下边这部分是反转链表的第一组的k个节点
            cur = head;
            ListNode next;
            while (i-- > 0) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
}

[liuxinhaen]

这小节同样很精彩，感谢

[yonggui-yan]

递归调用reverseKGroup，每次递归中若达到k个则调用reverseK返回NewHead 否则直接返回Head。

递归想法：reverse前k个后，后面的仍然可看着k个一组反转链表

[xxxsod1]

好优美，我哭了

[xueerfei]

用之前的翻转前N个链表实现

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode a=head, b=head;
        for(int i=0; i<k;i++){
            if(b == null){//不满足K个，不反转
                return head;
            }
            b = b.next;
        }
        ListNode newHead = reverseN(head, k); //翻转前K个
        //将前K个翻转之后，重新连接到下一组上
        head.next = reverseKGroup(b, k);
        return newHead;
    }

    ListNode last = null;

    //反转前N个链表
    ListNode reverseN(ListNode head, int n){
        if(head == null){
            last = null;
            return null;
        }
        if(n == 1){
            last = head.next;
            return head;
        }

        ListNode next = reverseN(head.next, n-1);
        head.next.next = head;
        head.next = last;
        return next;
    }
}

[saw008]

自己的解法，纯粹迭代，无额外空间

class Solution:
    # Time O(n) | Space O(1)
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reverseK(head, k):
            # to probe if remaining list has at least k nodes
            tmp_count = 0
            tmp_cur = head.next
            while tmp_count < k:
                if tmp_cur is None:
                    return None
                tmp_cur = tmp_cur.next
                tmp_count += 1
            prev_tail = head
            count = 0
            cur = head.next
            prev = head
            next_ = None
            while count < k:
                next_ = cur.next
                cur.next = prev
                prev = cur
                cur = next_
                count += 1
            new_prev_tail = prev_tail.next
            prev_tail.next = prev
            new_prev_tail.next = cur
            return new_prev_tail
            
        dummy = ListNode(-1, head)
        prev = dummy
        while prev is not None:
            prev = reverseK(prev, k)
        return dummy.next