Reversing a LinkedList with a random Pointer


  • 0
    H

    My friend who attended an onsite interview told me this question. I keep getting stumped on O(1) space complexity. Without that space constraint, my solution revolved around using a HashMap that stores the jump pointers while traversing and reversing. Would love to hear your thoughts or solutions?


    Consider a Singly Linked List, in addition to having a typical 'next' pointer, it also has a 'jump' pointer.
    The 'jump' pointer points to some random other Node on the linked list. The jump pointer can also be NULL

    You are required to reverse the direction of all 'next' and 'jump' pointers. Can you do this in O(1) space complexity?


  • 0
    H

    @Hack3r

    Here is my attempt at that solution.

    static Node<E> reverseList(Node<E> head) {
    if(head == null || head.next == null) {
    return head;
    }

    Node<Integer> current = head;
    Node temp = null;

    // Reverse an existing Linked list.
    while(current != null) {
    Node previousNext = current.next;
    current.next = temp;
    temp = current;
    current = previousNext;
    }

    reversedHead = temp;
    while(temp != null) {
    if(temp.jump != null) {
    Node jumpTemp = temp.jump;
    jumpTemp.jump = temp;
    temp.jump = null;
    }
    temp = temp.next;
    }

    return reversedHead;
    }


  • 3
    E

    @Hack3r
    I was starting with a similar approach but this will not work as it will re-reverse the jump pointer for pointers that point to nodes further down the chain. For instance if you had the chain going from 1 -> 2 -> 3 and 1 has a jump pointer to 3, you'll be reversing the jump ptr twice, once at 1 and the second time at 3. Same will apply if there's a ptr going backwards originally (say from 3 to 1 in the example earlier). Once you reverse the list to the state of 1 <- 2 <- 3, you'll again be double reversing the ptr from 3 to 1, once at 3 and the second time at 1.


  • -1
    M
    This post is deleted!

  • 0
    E

    @mzeus.bolt Is this to clone a list? Looks like you've copied and pasted code from GeeksForGeeks for that problem which is an entirely different problem from this.


  • 0
    G

    how about record the number of connected components formed by random edges. for every component, reverse the edges from the end to the start (loop is from one direction of the node to the other). when your counter is 0 you know you can terminate.


  • 0
    M

    @Ellest Yes Its for reference


  • 0
    E

    @gyzjay Not sure if I follow. How would you define the end of a connected component?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.