LeetCode25——K个一组反转链表

最近忙着看东西,抽不出时间来写博客记录自己总结的东西,有种想一吐为快的感觉,先过完这段时间吧!先匆忙记录下这道题。同时也希望自己在这个春招能收到满意的offer!加油吧!

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

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

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

以下解法是leetcode上大佬的解法,我参照着学习和写下自己的理解!

看图说话:

k个一组翻转链表

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        
        if(head == null || head.next == null){
            return head;
        }
        // 创建伪造节点,并指向head
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode pre = dummy;
        ListNode end = dummy;

        while(end.next!=null){
            // 让end节点移动到第k个node
          for(int i=0;i<k && end!=null;i++){
             end = end.next;
           } 
            // 不够ke个节点,不反转,跳出循环
           if(end==null){
               break;
           }
            // 记住下一个节点,为下一次反转作准备
           ListNode next = end.next;
            // 开始节点为pre.next
           ListNode start = pre.next;
            //反转之前斩断联系,不要藕断丝连
           end.next = null;
           pre.next = reverst(start);
            //第一个成为最后一个,找回联系
           start.next = next;
            //改变pre,end的位置
           pre = start;
           end = start;
        }
        return dummy.next;
    }

    // 反转链表的函数,不懂的话,自己手动画图,一图胜千言
    public ListNode reverst(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            //局部反转完成,转移阵地
            pre = cur;
            cur = next;
        }
        // 当cur==null时,pre即为头节点
        return pre;
    }
}
end

评论