Teaching Kids Programming: Videos on Data Structures and Algorithms
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULLFollow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Iterative Algorithm to Reverse a Linked List
We keep updating the previous node and current node along the linked list, and reverse the link directions e.g. pointing the current node to previous node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: prev = None cur = head while cur: nextTemp = cur.next cur.next = prev prev = cur cur = nextTemp return prev |
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
cur = head
while cur:
nextTemp = cur.next
cur.next = prev
prev = cur
cur = nextTemp
return prevTime complexity is O(N), where need to visit N nodes in the linked list. And Space requirement is O(1).
Recursive Algorithm to Reverse a Linked List
We can reverse this in Recursion manner. We can reverse every other nodes except current node, then reverse the link direction.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: if head is None or head.next is None: return head n = self.reverseList(head.next) head.next.next = head head.next = None return n |
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
n = self.reverseList(head.next)
head.next.next = head
head.next = None
return nThe Recursion can be tail optimised to O(N). The space complexity is O(N) where N is the number of the nodes in the linked list.
Reverse the LinkList by Changing the Node Value
If we are allowed to change the node values, we don’t need to modify the link directions. We can then go through the linked list twice. The first time we copy the node values to an array, the second time we assign the node values (in reversed order) to each node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: data = [] p = head while p: data.append(p.val) p = p.next p = head while p: p.val = data.pop() p = p.next return head |
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
data = []
p = head
while p:
data.append(p.val)
p = p.next
p = head
while p:
p.val = data.pop()
p = p.next
return headRelated Posts
- How to Reverse Linked List within Interval? (C/C++)
- How to Print Immutable Linked List in Reverse using Recursion or Stack?
- How to Reverse a Linked List in Javascript?
- How to Reverse a Linked List in C/C++?
–EOF (The Ultimate Computing & Technology Blog)
loading...
Last Post: Binary Search Algorithm to Find the Fixed Point
Next Post: Split a Set into Two with Equal Sums and Distinct Numbers
