# Reversing a LinkedList with a random Pointer

• 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?

• @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; }```

• @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.

• This post is deleted!

• @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.

• 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.

• @Ellest Yes Its for reference

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

• to

let's say we have 3 nodes, 1 -> 2 -> 3
first copy each of the nodes and append them like 1 -> c1 -> 2 -> c2 -> 3 -> c3 where c* represents the copied one.
assume 3.jump = 1, you can reverse it by setting
3.jump.next.jump = 3.next

in general, for each node n,
n.jump.next.jump = n.next

• @hhyuan.f Note that the requirement asks for a solution with O(1) space complexity. Copying each node will result in O(n) extra space.

• @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; }```

By jumpTemp.jump = temp; the code has discarded any information stored in jumpTemp.jump. Also, going through temp.next can potentially reversed the randomly linked list back to original.

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