0206. Reversed Linked List

0206. Reversed Linked List#

Problem#

Given the head of a singly linked list, reverse the list, and return the reversed list.

Examples#

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:#

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Follow-up#

Analysis#

If swaping values in the nodes are allowed, we dont need swap nodes that requires the update of next pointer. However, if the value in a node is not writable, then we will have to swap nodes. The following solutions swap nodes instead of only values.

Solution 1#

  • create a empty linked list to store reversed list

  • attach each node iteratively to the reversed list

    • the node is the head, pointing to the previous reversed list

Example:

list = [1,2,3,4,5]

step 0: new_head
step 1: node = 1, new_head.next = node -> reversed_list = [1]
step 2: node = 2, prev = new_head.next, new_head.next = node, node.next = prev -> reversed_list = [2, 1]
...

Solution 2#

# some definitions
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val 
        self.next = next 

def list_to_linkedlist(list):
    head = ListNode()
    node = head
    for v in list:
        v_node = ListNode(v)
        node.next = v_node
        node = node.next

    return head.next

def print_linkedlist(linked_list):
    res = []
    while linked_list:
        res.append(linked_list.val)
        linked_list = linked_list.next
    print(res)
    
list = [1,2,3,4,5]
head = list_to_linkedlist(list)
print_linkedlist(head)

[1, 2, 3, 4, 5]

# solution 1: two pointers O(N) in time, and O(1) in space
# one for current node, and the other for previous node
# 1-2-3-4-5 -> 1-2-3-4-5 -> 2-1 3-4-5 -> 3-2-1 4-5 -> 4-3-2-1 5 -> 5-4-3-2-1

def solution(head):
    # initialize current and previous pointer
    prev, cur = None, head

    # main loop
    while cur:
        # save for future use as the original link between cur and cur.next will be destroied later.
        next = cur.next 
        cur.next = prev

        # move forward
        prev = cur
        cur = next 

    return prev

#test
list = list_to_linkedlist([1,2,3,4,5])
print_linkedlist(solution(list))

list = list_to_linkedlist([5])
print_linkedlist(solution(list))

list = list_to_linkedlist([])
print_linkedlist(solution(list))

list = list_to_linkedlist([2,5])
print_linkedlist(solution(list))

[5, 4, 3, 2, 1]
[5]
[]
[5, 2]

# solution 2: how to use two pointer method with a dummy node
# this method actually complicates the solution compared with solution 1

def solution(head):
    # add a dummy node the original list
    dummy = ListNode(next=head)

    prev, cur = dummy, dummy.next 
    tail = cur 

    while cur:
        next = cur.next
        cur.next = prev 
        prev = cur 
        cur = next 
    
    if tail:
        tail.next = cur 

    return prev

#test
list = list_to_linkedlist([1,2,3,4,5])
print_linkedlist(solution(list))

list = list_to_linkedlist([5])
print_linkedlist(solution(list))

list = list_to_linkedlist([])
print_linkedlist(solution(list))

list = list_to_linkedlist([2,5])
print_linkedlist(solution(list))

[5, 4, 3, 2, 1]
[5]
[0]
[5, 2]

# solution 3: how to use a dummy node for this kind of problem O(N) in time and O(1)
# iteratively add the first node in the orignal list to the dummay list as the second node

def solution(head):
    # add a dummy node for the linked list
    # this is a typical approach when the head of the original list may be modified.
    dummy = ListNode()

    # initialize current and previous pointer
    cur = head

    # main loop
    while cur:
        # save for future use as the original link between cur and cur.next will be destroied later.
        prev = dummy.next 
        dummy.next = cur
        
        # move forward
        cur = cur.next
        dummy.next.next = prev
        
    return dummy.next

#test
list = list_to_linkedlist([1,2,3,4,5])
print_linkedlist(solution(list))

list = list_to_linkedlist([5])
print_linkedlist(solution(list))

list = list_to_linkedlist([])
print_linkedlist(solution(list))

list = list_to_linkedlist([2,5])
print_linkedlist(solution(list))

[5, 4, 3, 2, 1]
[5]
[]
[5, 2]

# solution 2: iterative solution, which is same as previous solution except that the dummy node is not used here.
# [1-2-3-4-5] -> 1 -> 2-1 -> 3-2-1 -> 4-3-2-1 -> 5-4-3-2-1
def solution(head):
    newHead = None

    while head:
        previous = newHead #4
        newHead = head # 5
        
        # update iterator
        head = head.next # this has to be ahead of the next code 
        newHead.next = previous # 

    return newHead 

 #test
list = list_to_linkedlist([1,2,3,4,5])
print_linkedlist(solution(list))

list = list_to_linkedlist([5])
print_linkedlist(solution(list))

list = list_to_linkedlist([])
print_linkedlist(solution(list))

list = list_to_linkedlist([2,5])
print_linkedlist(solution(list))

[5, 4, 3, 2, 1]
[5]
[]
[5, 2]

# Solution 3; recursive solution
# 1-2-3-4-5 -> 5 -> 5-4 -> 5-4-3 -> 5-4-3-2 -> 5-4-3-2-1
def solution(head):
    # return 
    if not head or not head.next:
        return head

    # update recusion
    newHead = solution(head.next) # this newHead is always 5
    head.next.next = head # why not newHead.next = next? because newHead is always 5, update newHead.NEXT will be liking removing the resest after 5.
    head.next = None
    
    return newHead

 #test
list = list_to_linkedlist([1,2,3,4,5])
print_linkedlist(solution(list))  

[5, 4, 3, 2, 1]
Contents