Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 2: Rearrange a LinkedList (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next
class Solution:
  def reorder(self, head):
    
    def find_mid(head):
      slow, fast = head, head 
      while slow and fast:
        if fast:
          if fast.next:
            fast = fast.next.next
          else:
            return slow
        else:
          return slow
        slow = slow.next
      return slow
    
    def reverse(node):
      prev = None
      while node:
        next_node = node.next
        node.next = prev
        prev = node
        node = next_node
      return prev 

    # Find the middle and last points then reverse linked list from the middle to the end
    start = head
    mid = find_mid(head)
    last = reverse(mid)

    # Construct the new
A

Anonymous

· 3 years ago

I think the wording that says we should not be using any extra space is a bit confusing and should either be reworded or removed. It made me think I could not create more than 2 pointer variables when I should be able to create first and second half variables to actually finish the solution.

Show 2 replies
A

Anonymous

· 3 years ago

  if head_first_half is not None:
    head_first_half.next = None

I am having trouble understanding why this portion of the code is needed at all. Why do we not have to do the same if statement for the head_second_half?

Show 1 reply
A

Anonymous

· 4 years ago

I have a question, might be dumb but I'm gonna ask anyway. I'm supposed to learn try every problem before checking the solution or I'm supposed to learn the patterns and that's it?

Show 1 reply
A

Anonymous

· 5 years ago

Prior to exiting the while loop that rearranges the LinkedList, would the last node be pointing to itself? For instance, if we had 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> null, and it's rearranged to 2 -> 12 -> 4 -> 10 -> 6 -> 8 , then before the lines (Java): if (headFirstHalf != null) headFirstHalf.next = null; would the 8 node be pointing to itself? I'm having a tough time visualizing this part.

Show 4 replies
A

Anonymous

· 5 years ago

Can someone explain the logic to the rearange to produce the linkedlist in required order part? ListNode temp = headFirstHalf.next; headFirstHalf.next = headSecondHalf; headFirstHalf = temp;

temp = headSecondHalf.next; headSecondHalf.next = headFirstHalf; headSecondHalf = temp;

I cant wrap my brain around it. Maybe I don't quite understand how each of these change the actual head. Are all of these working directly on ListNode Head and not copies? I'm using java.

Show 2 replies

Reading Progress

0%

Vote for new content