Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
按照k循环模式进行替换
分两步进行，
找到每一个k循环的结尾，如果结尾不空 进行翻转操作，翻转操作只在局部进行 所以先把这一小部分的下一个节点置空
然后将所有的辅助指针放到下一个小局部的开头
public class Solution { public ListNode reverseKGroup(ListNode head, int k) { if(head==null||head.next==null) return head; ListNode dummy=new ListNode(-1); dummy.next=head; ListNode preHead=dummy,tail=dummy,postTail=dummy; int count=0; while(tail!=null){ if(count==k){ count=0; postTail=tail.next; tail.next=null; //置空局部链表末尾 preHead.next=reverse(head); head.next=postTail; preHead=head; tail=head; head=head.next; } tail=tail.next; count++; } return dummy.next; } public ListNode reverse(ListNode head){ if(head==null||head.next==null) return head; ListNode newhead=new ListNode(-1); while (head!=null){ ListNode temp=head; head=head.next; temp.next=newhead; newhead=temp; } return newhead; } } 一种递归的方法 实质上是相同的思路 public class Solution { public ListNode reverseKGroup(ListNode head, int k) { if(head == null || head.next == null || k <= 1) return head; ListNode kthNode = head; int count = 1; while(count < k) { if(kthNode == null) return head; kthNode = kthNode.next; count++; } if(kthNode == null) return head; ListNode kplusoneNode = kthNode.next; kthNode.next = null; ListNode newHead = reverse(head); head.next = reverseKGroup(kplusoneNode, k); return newHead; } private ListNode reverse(ListNode head) { if(head == null || head.next == null) return head; ListNode dummy = new ListNode(-1); while(head != null) { ListNode tmp = head.next; head.next = dummy.next; dummy.next = head; head = tmp; } return dummy.next; } }
