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

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

示例 :

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

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

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

说明 :

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

这个题目其实就是92. 反转链表 II这个题目的改进版,我们只需要按K进行分组,每组进行链表反转即可。
解法如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public static ListNode reverse(ListNode first,ListNode last){
        ListNode cur = first.next;
        ListNode next = cur.next;
        while(next!=last){
            cur.next = next.next;
            next.next = first.next;
            first.next = next;
            next = cur.next;
        }
        return cur;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode h = new ListNode(-1);
        h.next = head;
        ListNode pre = h;
        ListNode cur = head;
        int count = 1;
        while(cur!=null){
            if(count%k==0){
                pre = reverse(pre,cur.next);
                cur = pre.next;
            }else{
                cur = cur.next; 
            }
            count++;
        }
        return h.next;
    }
}
Last modification:April 30th, 2019 at 03:59 am
大家一起分享知识,分享快乐