Back to Front Linked List
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
wheren
is the number of nodes innode
https://binarysearch.com/problems/Back-to-Front-Linked-List
ExamplesPermalink
Example 1Permalink
Input
- node =
Output
- answer =
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