Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 2: Rearrange a LinkedList

Problem Statement

Given the head of a Singly LinkedList, write a method to modify the LinkedList such that the nodes from the second half of the LinkedList are inserted alternately to the nodes from the first half in reverse order. So if the LinkedList has nodes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null, your method should return 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null.

Your algorithm should use only constant space the input LinkedList should be modified in-place.

Example 1:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> null
Output: 2 -> 12 -> 4 -> 10 -> 6 -> 8 -> null

Example 2:

.....

.....

.....

Like the course? Get enrolled and start learning!
E

Eric C

· 4 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
J

Justin Cook

· 4 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
Jan Carlos Dominguez

Jan Carlos Dominguez

· 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
M

Master Account

· 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
D Delg

D Delg

· 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
Mohammed Dh Abbas

Mohammed Dh Abbas

· 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