[leetcode]算法題目 - Reverse Nodes in k-Group
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
分析：
鏈表操作，本身用不上什么高大上的算法或者數據結構。不過其中那些繁雜的小細節很容易搞得頭大，很少能有人把這種題目一次寫對吧。更可恨的是，就算寫完了，隔一天在看自己之前寫的思路，依然要費好多腦細胞才能理清楚。。。。。
這道題的思路是，先計算出來鏈表的長度len，然后len除以k就得到我們總共需要反轉幾個子鏈表。反轉鏈表的操作本身不難，難的在于兩個子鏈表銜接的部分。你必須要記錄清楚這個子鏈表的尾巴和頭部，并在合適的時機設置它們指向的節點……總之很難用文字描述清楚，直接上代碼吧。。就這么幾行代碼折騰了倆小時才搞定。
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public ListNode reverseKGroup(ListNode head, int k) { 14 int len = 0; 15 ListNode headbp = head; 16 while(headbp != null){ 17 len++; 18 headbp = headbp.next; 19 } 20 if(len < 2){return head;} 21 22 int reverseTimes = (len / k); 23 24 ListNode myhead = new ListNode(0); 25 myhead.next = head; 26 ListNode curr = myhead; 27 ListNode next = head; 28 ListNode prev = null; 29 ListNode rhead = curr; 30 ListNode rtail = curr.next; 31 32 for(int j=0;j<reverseTimes;j++){ 33 rhead = curr; 34 rtail = curr.next; 35 curr = curr.next; 36 next = curr; 37 for (int i = 0; i < k; i++) { 38 next = next.next; 39 curr.next = prev; 40 prev = curr; 41 curr = next; 42 } 43 rhead.next = prev; 44 rtail.next = next; 45 prev = null; 46 curr = rtail; 47 } 48 return myhead.next; 49 } 50 }
浙公網安備 33010602011771號