Reverse a Linked List in groups of given size | GeeksforGeeks
Given a linked list, write a function to reverse every k nodes (where k is an input to the function).
Iterative Version
From http://www.cnblogs.com/lichen782/p/leetcode_Reverse_Nodes_in_kGroup.html
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list.
http://algorithms.tutorialhorizon.com/reverse-a-linked-list-in-groups-of-given-size-k/
int x = k;
Node head_next=null;
Node h = head;
Node head_prev = null;
while(h!=null && x>0){
head_next = h.next;
h.next = head_prev;
head_prev = h;
h = head_next;
x--;
}
if(head_next!=null){
head.next = reveseGrps(head_next,k);
}
return head_prev;
}
Read full article from Reverse a Linked List in groups of given size | GeeksforGeeks
Given a linked list, write a function to reverse every k nodes (where k is an input to the function).
Iterative Version
From http://www.cnblogs.com/lichen782/p/leetcode_Reverse_Nodes_in_kGroup.html
1 public static ListNode reverseKGroup2(ListNode head, int k) { 2 if(head == null || k == 1) return head; 3 ListNode dummy = new ListNode(0); 4 dummy.next = head; 5 ListNode pre = dummy; 6 int i = 0; 7 while(head != null){ 8 i++; 9 if(i % k ==0){ 10 pre = reverse(pre, head.next); 11 head = pre.next; 12 }else { 13 head = head.next; 14 } 15 } 16 return dummy.next; 17 }
private static ListNode reverse(ListNode pre, ListNode next){ ListNode last = pre.next;//where first will be doomed "last" ListNode cur = last.next; while(cur != next){ last.next = cur.next; cur.next = pre.next; pre.next = cur; cur = last.next; } return last; }Recursive version
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list.
struct
node *reverse (
struct
node *head,
int
k)
{
struct
node* current = head;
struct
node* next;
struct
node* prev = NULL;
int
count = 0;
/*reverse first k nodes of the linked list */
while
(current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if
(next != NULL)
{ head->next = reverse(next, k); }
/* prev is new head of the input list */
return
prev;
}
- Reverse first ‘k’ nodes of the linked list, the kth node will be a new head, return it.
- Make a recursive call to rest of the list and attach it to the last node.(See the picture below)
int x = k;
Node head_next=null;
Node h = head;
Node head_prev = null;
while(h!=null && x>0){
head_next = h.next;
h.next = head_prev;
head_prev = h;
h = head_next;
x--;
}
if(head_next!=null){
head.next = reveseGrps(head_next,k);
}
return head_prev;
}
Read full article from Reverse a Linked List in groups of given size | GeeksforGeeks