K 个一组翻转链表( LeetCode 25 )

一、题目描述

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// K 个一组翻转链表( LeetCode 25 ) :https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 一开始设置一个虚拟节点,它的值为 -1,它的值可以设置为任何的数,因为我们根本不需要使用它的值
        ListNode dummy = new ListNode(-1);

        // 虚拟头节点的下一节点指向 head 节点
        // 如果原链表是  1 -->  2 -->  3
        // 那么加上虚拟头节点就是  -1 -->  1 -->  2 -->  3

        dummy.next = head;

        // 设置一个指针,指向此时的虚拟节点,pre 表示每次要翻转的链表的头结点的【上一个节点】
        // pre: -1 -->  1 -->  2 -->  3
        ListNode pre = dummy;

        // 设置一个指针,指向此时的虚拟节点,end 表示每次要翻转的链表的尾节点
        // end: -1 -->  1 -->  2 -->  3
        ListNode end = dummy;

        // 通过 while 循环,不断的找到翻转链表的尾部
        while( end.next != null){

            // 通过 for 循环,找到【每一组翻转链表的尾部】
            // 由于原链表按照 k 个一组进行划分会可能出现有一组的长度不足 k 个
            // 比如原链表 1 -->  2 -->  3 -->  4 -->  5
            // k = 2,划分了三组 1 -->  2, 3 -->  4, 5
            // 所以得确保 end 不为空才去找它的 next 指针,否则 null.next 会报错
            for(int i = 0 ; i < k && end != null ; i++){
                // end 不断的向后移动,移动 k 次到达【每一组翻转链表的尾部】
                end = end.next ;
            }

            // 如果发现 end == null,说明此时翻转的链表的节点数小于 k ,保存原有顺序就行
            if(end == null){
                // 直接跳出循环,只执行下面的翻转操作
                break;
            }


            // next 表示【待翻转链表区域】里面的第一个节点
            ListNode next = end.next;

            // 【翻转链表区域】的最尾部节点先断开
            end.next = null ;

            // start 表示【翻转链表区域】里面的第一个节点
            ListNode start = pre.next;



            // 【翻转链表区域】的最头部节点和前面断开
            pre.next = null;

            // 这个时候,【翻转链表区域】的头节点是 start,尾节点是 end
            // 开始执行【反转链表】操作
            // 原先是 start --> ...--> end
            // 现在变成了 end --> ...--> start

            // 要翻转的链表的头结点的【上一个节点】的 next 指针指向这次翻转的结果
            pre.next = reverse(start);

            // 接下来的操作是在为【待翻转链表区域】的反转做准备

            // 原先是 start --> ...--> end
            // 现在变成了 end --> ...--> start
            // 【翻转链表区域】里面的尾节点的 next 指针指向【待翻转链表区域】里面的第一个节点
            start.next = next ;

            // 原先是 start --> ...--> end
            // 现在变成了 end --> ...--> start
            // pre 表示每次要翻转的链表的头结点的【上一个节点】
            pre = start;

            // 将 end 重置为【待翻转链表区域】的头结点的上一个节点。
            end = start;
        }
        return dummy.next;


    }
    // 反转链表的代码
    private ListNode reverse(ListNode head) {
        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下,反转之后的结果还是它自己本身
        if( head == null || head.next == null)  return head;

        // 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        ListNode cur = reverse(head.next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候,head 为 4,那么 head.next = 5
        // 那么 head.next.next 就是 5.next ,意思就是去设置 5 的下一个节点
        // 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head;


        // head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head.next = null;

        // 我们把每次反转后的结果传递给上一层
        return cur;

    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// K 个一组翻转链表( LeetCode 25 ) :https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
class Solution {
public:
       ListNode* reverseKGroup(ListNode* head, int k) {
                 // 一开始设置一个虚拟节点,它的值为 -1,它的值可以设置为任何的数,因为我们根本不需要使用它的值
                 ListNode* dummy = new ListNode(-1);

                 // 虚拟头节点的下一节点指向 head 节点
                 // 如果原链表是  1 -->  2 -->  3
                 // 那么加上虚拟头节点就是  -1 -->  1 -->  2 -->  3

                 dummy->next = head;

                 // 设置一个指针,指向此时的虚拟节点,pre 表示每次要翻转的链表的头结点的【上一个节点】
                 // pre: -1 -->  1 -->  2 -->  3
                 ListNode* pre = dummy;

                 // 设置一个指针,指向此时的虚拟节点,end 表示每次要翻转的链表的尾节点
                 // end: -1 -->  1 -->  2 -->  3
                 ListNode* end = dummy;

                 // 通过 while 循环,不断的找到翻转链表的尾部
                 while( end->next != NULL){

                     // 通过 for 循环,找到【每一组翻转链表的尾部】
                     // 由于原链表按照 k 个一组进行划分会可能出现有一组的长度不足 k 个
                     // 比如原链表 1 -->  2 -->  3 -->  4 -->  5
                     // k = 2,划分了三组 1 -->  2, 3 -->  4, 5
                     // 所以得确保 end 不为空才去找它的 next 指针,否则 NULL->next 会报错
                     for(int i = 0 ; i < k && end != NULL ; i++){
                         // end 不断的向后移动,移动 k 次到达【每一组翻转链表的尾部】
                         end = end->next ;
                     }

                     // 如果发现 end == NULL,说明此时翻转的链表的节点数小于 k ,保存原有顺序就行
                     if(end == NULL){
                         // 直接跳出循环,只执行下面的翻转操作
                         break;
                     }


                     // next 表示【待翻转链表区域】里面的第一个节点
                     ListNode* next = end->next;

                     // 【翻转链表区域】的最尾部节点先断开
                     end->next = NULL ;

                     // start 表示【翻转链表区域】里面的第一个节点
                     ListNode* start = pre->next;



                     // 【翻转链表区域】的最头部节点和前面断开
                     pre->next = NULL;

                     // 这个时候,【翻转链表区域】的头节点是 start,尾节点是 end
                     // 开始执行【反转链表】操作
                     // 原先是 start --> ->--> end
                     // 现在变成了 end --> ->--> start

                     // 要翻转的链表的头结点的【上一个节点】的 next 指针指向这次翻转的结果
                     pre->next = reverse(start);

                     // 接下来的操作是在为【待翻转链表区域】的反转做准备

                     // 原先是 start --> ->--> end
                     // 现在变成了 end --> ->--> start
                     // 【翻转链表区域】里面的尾节点的 next 指针指向【待翻转链表区域】里面的第一个节点
                     start->next = next ;

                     // 原先是 start --> ->--> end
                     // 现在变成了 end --> ->--> start
                     // pre 表示每次要翻转的链表的头结点的【上一个节点】
                     pre = start;

                     // 将 end 重置为【待翻转链表区域】的头结点的上一个节点。
                     end = start;
                   }

                    return dummy->next;


       }
 // 反转链表的代码
private:
        ListNode* reverse(ListNode* head) {
                  // 寻找递归终止条件
                  // 1、head 指向的结点为 NULL 
                  // 2、head 指向的结点的下一个结点为 NULL 
                  // 在这两种情况下,反转之后的结果还是它自己本身
                  if( head == NULL || head->next == NULL)  return head;

                  // 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
                  // 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
                  ListNode* cur = reverse(head->next);

                  // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
                  // 第一次执行下面代码的时候,head 为 4,那么 head->next = 5
                  // 那么 head->next->next 就是 5->next ,意思就是去设置 5 的下一个节点
                  // 等号右侧为 head,意思就是设置 5 的下一个节点是 4

                  // 这里出现了两个 next
                  // 第一个 next 是「获取」 head 的下一节点
                  // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
                  head->next->next = head;


                  // head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
                  // 否则会发生无限循环
                  head->next = NULL;

                  // 我们把每次反转后的结果传递给上一层
                  return cur;

 }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# K 个一组翻转链表( LeetCode 25 ) :https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # 一开始设置一个虚拟节点,它的值为 -1,它的值可以设置为任何的数,因为我们根本不需要使用它的值
        dummy = ListNode(-1)

        # 虚拟头节点的下一节点指向 head 节点
        # 如果原链表是  1 -->  2 -->  3
        # 那么加上虚拟头节点就是  -1 -->  1 -->  2 -->  3

        dummy.next = head

        # 设置一个指针,指向此时的虚拟节点,pre 表示每次要翻转的链表的头结点的【上一个节点】
        # pre: -1 -->  1 -->  2 -->  3
        pre = dummy

        # 设置一个指针,指向此时的虚拟节点,end 表示每次要翻转的链表的尾节点
        # end: -1 -->  1 -->  2 -->  3
        end = dummy

        # 通过 while 循环,不断的找到翻转链表的尾部
        while end.next != None :

            # 通过 for 循环,找到【每一组翻转链表的尾部】
            # 由于原链表按照 k 个一组进行划分会可能出现有一组的长度不足 k 个
            # 比如原链表 1 -->  2 -->  3 -->  4 -->  5
            # k = 2,划分了三组 1 -->  2, 3 -->  4, 5
            # 所以得确保 end 不为空才去找它的 next 指针,否则 None.next 会报错
            for i in range(k) :
                if end is None:
                   break
                else:
                   # end 不断的向后移动,移动 k 次到达【每一组翻转链表的尾部】
                   end = end.next 

            # 如果发现 end == None,说明此时翻转的链表的节点数小于 k ,保存原有顺序就行
            if end is None:
                # 直接跳出循环,只执行下面的翻转操作
                break


            # next 表示【待翻转链表区域】里面的第一个节点
            next = end.next

            # 【翻转链表区域】的最尾部节点先断开
            end.next = None 

            # start 表示【翻转链表区域】里面的第一个节点
            start = pre.next



            # 【翻转链表区域】的最头部节点和前面断开
            pre.next = None

            # 这个时候,【翻转链表区域】的头节点是 start,尾节点是 end
            # 开始执行【反转链表】操作
            # 原先是 start --> ...--> end
            # 现在变成了 end --> ...--> start

            # 要翻转的链表的头结点的【上一个节点】的 next 指针指向这次翻转的结果
            pre.next = self.reverseList(start)

            # 接下来的操作是在为【待翻转链表区域】的反转做准备

            # 原先是 start --> ...--> end
            # 现在变成了 end --> ...--> start
            # 【翻转链表区域】里面的尾节点的 next 指针指向【待翻转链表区域】里面的第一个节点
            start.next = next 

            # 原先是 start --> ...--> end
            # 现在变成了 end --> ...--> start
            # pre 表示每次要翻转的链表的头结点的【上一个节点】
            pre = start

            # 将 end 重置为【待翻转链表区域】的头结点的上一个节点。
            end = start

        return dummy.next


    # 反转链表的代码
    def reverseList(self,head:ListNode) -> ListNode:
        # 寻找递归终止条件
        # 1、head 指向的结点为 None 
        # 2、head 指向的结点的下一个结点为 None 
        # 在这两种情况下,反转之后的结果还是它自己本身
        if head == None or head.next == None:
           return head

        # 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        # 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        cur = self.reverseList(head.next)


        # 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        # 第一次执行下面代码的时候,head 为 4,那么 head.next = 5
        # 那么 head.next.next 就是 5.next ,意思就是去设置 5 的下一个节点
        # 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        # 这里出现了两个 next
        # 第一个 next 是「获取」 head 的下一节点
        # 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head


        # head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        # 否则会发生无限循环
        head.next = None

        # 我们把每次反转后的结果传递给上一层
        return cur

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注