less than 1 minute read

Given a singly linked list node, reorder it such that we take: the last node, and then the first node, and then the second last node, and then the second node, etc.

Can you do it in O(1) space?

Constraints

  • 0 ≤ n ≤ 100,000 where n is the number of nodes in node

https://binarysearch.com/problems/Back-to-Front-Linked-List

ExamplesPermalink

Example 1Permalink

Input

  • node =
example1Node 0 0 1 1 0->1 2 2 1->2 3 3 2->3

Output

  • answer =
example1Output 0 3 1 0 0->1 2 2 1->2 3 1 2->3

SolutionPermalink

# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def solve(self, node):
if not node:
return None
lst = []
while node:
lst.append(node)
node = node.next
ordered = [lst.pop(0 if i % 2 else -1) for i in range(len(lst))]
for (a, b) in zip(ordered, ordered[1:]):
a.next = b
ordered[-1].next = None
return ordered[0]

Leave a comment