LeetCodeOnlineJudge题目C#练习-ReverseNodesink-Group

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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

 1         public static LinkedListNode ReverseNodesinkGroupOpt(LinkedListNode head, int k)
 2         {
 3             if (k <= 1)
 4                 return head;
 5 
 6             LinkedListNode fakehead = new LinkedListNode();
 7             fakehead.Next = head;
 8             LinkedListNode prev_tail = fakehead;
 9             LinkedListNode curr = head;
10             LinkedListNode next = head;
11             LinkedListNode tail = head;
12 
13             while (curr != null)
14             {
15                 for (int i = 1; i < k; i++)
16                 {
17                     curr = curr.Next;
18                     if (curr == null)
19                         return fakehead.Next;
20                     next = curr.Next;
21                 }
22 
23                 curr.Next = null;
24                 ReverseSignlyLinkedListIterative(tail);
25 
26                 prev_tail.Next = curr;
27                 prev_tail = tail;
28                 tail.Next = next;
29                 curr = next;
30                 tail = next;
31             }
32 
33             return fakehead.Next;
34         }

代码分析：

　　虽然这题操作到head不是corner case，但是我还是加了一个fakehead在前面，模拟前面一个sub linked list的tail， prev_tail。非常方便，如果k 大于linkedlist长度，返回的是fakehead.Next, 就是head。如果k 小于 linkedlist 长度，fakehead.Next 将会指向第一个sub list的 head。