LeetCode [25] 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.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

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

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126

]/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if (k < 2) return head; ListNode *H = new ListNode(0); H->next = head; ListNode *IH = H; //Interval Head while (IH) { if (IH->next == NULL || IH->next->next == NULL) break; ListNode *IHn = IH->next; //next IH ListNode *p = IH->next->next; int len = 0; //count real length bool undo = false; for (int i = 0; i < k - 1; ++i) { if (p == NULL) { k = len + 1; undo = true; break; } ListNode *q = p->next; len++; p->next = IH->next; IH->next = p; p = q; } if (!undo) IH = IHn; IHn->next = p; } return H->next; } }; class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if(!head || !head->next || k<=1) return head; ListNode *H = new ListNode(0); H->next = head; ListNode *pre = H; ListNode *start = pre->next; ListNode *end = start; ListNode *p = start->next; ListNode *next; bool endofcycle = true; int i; while(p){ i=0; for(i; i<k-1 && p; ++i){ endofcycle = false; next = p->next; pre->next = p; p->next = start; end->next = next; start = p; p = next; if(i==k-2){ endofcycle = true; if(!end||!end->next) break; pre = end; start = pre->next; end = start; p = start->next; } } } if(!endofcycle){ start = p; p=pre->next; while(p&&p!=end){ pre->next = p->next; end->next = p; p->next = start; start = p; p = pre->next; } } return H->next; } }; class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if(k<=1 || !head) return head; ListNode *H = new ListNode(0), *p1, *p2 = head, *p = H; H->next = head; int i = 1; while(p2){ p1 = p2; int tail_id = i+k-1, j = i; while(p2 && p2->next && j<tail_id){p2 = p2->next; j++;} if(j<tail_id) break; ListNode *head_next = p2->next; ListNode *tail_pre = p1, *head_pre = p1, *next = p1->next;; for(j=i; j<tail_id; ++j){ p1 = next; next = p1->next; p->next = p1; p1->next = head_pre; head_pre = p1; } tail_pre->next = head_next; p2 = head_next; i = tail_id+1; p = tail_pre; } return H->next; } };