Advertisement
Iam_Sandeep

Reverse a Linked List in groups of given size.

Mar 24th, 2022
946
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.00 KB | None | 0 0
  1. https://leetcode.com/problems/reverse-nodes-in-k-group/
  2. 1.Amazing code with explanation
  3. 2.Mycode
  4. First:
  5.     class Solution:
  6.     def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
  7.         if not head or k == 1: return head
  8.         dummy = next_head = ListNode(None)
  9.         dummy.next = head
  10.         prev = curr = head
  11.  
  12.         while True:
  13.             count = 0
  14.             while curr and count < k:
  15.                 count += 1
  16.                 curr = curr.next
  17.             if count == k:
  18.                 h, t = curr, prev   # assign the first node of next k-group and the first node of current k-group to h(ead), t(ail)
  19.                 for _ in range(k):   # this is NOT a standard reversing by swapping arrows between adjacent nodes
  20.                     tmp = t.next     # instead it poplefts a node successively (ref. Campanula's comment)
  21.                     t.next = h
  22.                     h = t
  23.                     t = tmp
  24.                     # one-line implementation: t.next, t, h = h, t.next, t
  25.                 next_head.next = h   # connect the last node of the previous reversed k-group to the head of the current reversed k-group
  26.                 next_head = prev     # prepare for connecting to the next to-be-reversed k-group
  27.                 prev = curr   # head of the next yet to be reversed k-group
  28.             else:   # curr = None and count does not reach k i.e. list is exhausted
  29.                 return dummy.next
  30. Second:
  31.     class Solution:
  32.     def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
  33.         dummy=jump=ListNode(0)
  34.         l=r=head
  35.         while True:
  36.             c=0
  37.             while c<k and r:
  38.                 r=r.next
  39.                 c+=1
  40.             if c==k:#dont use r==None to check cut
  41.                 cur,pre=l,r
  42.                 for _ in range(k):
  43.                     cur.next,cur,pre=pre,cur.next,cur
  44.                 #pre is at
  45.                 jump.next,jump,l=pre,l,r
  46.             else:
  47.                 return dummy.next
  48.  
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement