Reverse a singly linked list.
Input: 1->2->3->4->5->NULL Output: NULL<-1<-2<-3<-4<-5
- A linked list can be reversed either iteratively or recursively. Could you implement both?
if to reverse a link list iteratively, need three pointers to store
- pre => previous node
- cur => current node
- nxt => next node (here nxt is different from node’s own next reference)
Iterate thru ll, for any given state:
- cur.next => pre
- pre => cur
- cur => nxt
- nxt => nxt.next
Below is the white board:
# Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseList(self, head): pre = ListNode(None) cur = head while cur is not None: #O(n) # store the current next node nxt = cur.next cur.next = pre # reverse the node pre = cur cur = nxt nxt = cur.next # now cur is None, pre is the last node from the original ll # pre is the head node for the new ll return pre def create_ll(nums): if len(nums) == 0: return None head = ListNode(nums) cur = head for num in nums[1:]: cur.next = ListNode(num) cur = cur.next return head def test_ll(): nums = list(range(5)) curr = create_ll(nums) while curr is not None: print(curr.val, end="=>") curr = curr.next print("None") test_ll()
- Time complexity is O(n)
Will try to figure out a recursive solution in the future.