正文
一、问题描述#
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5 当 k = 2 时,应当返回: 2->1->4->3->5 当 k = 3 时,应当返回: 3->2->1->4->5
说明:
你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
二、Java代码#
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode h, cur, pre,start; h = head; cur = head; start=null; pre=null; boolean isFirst = true; while (null != cur && null != cur.next) { ListNode[] kNode = new ListNode[k]; for (int i = k-1; i >=0 && null != cur; i--) { kNode[i] = cur; cur = cur.next; } if(kNode[0]!=null){ ListNode temp=kNode[0].next; start=kNode[0]; for (int i = 1; i < k && kNode[i] != null; i++) { start.next=kNode[i]; start=kNode[i]; } start.next=temp; if (isFirst) { h = kNode[0]; isFirst = false; pre=start; }else { pre.next=kNode[0]; pre=start; } } } return h; } }