Intuition The linked list is naturally in the reverse order we need to do the math. Keep a carry flag, special edge case at the final loop. Approach Traverse the linked list until there are no next elements in both lists. Sum both numbers, if carry is true, add 1 and set carry to false if > 9, set carry to true after the final iteration, if carry is true, add the last node with val = 1 ...
Intuition Traverse the list, saving the visited one to avoid cyclic loop. Approach A recursive function that Check if that node was visited, if it was, return visited. Create new node Saved new node in the visited (visited[curr] = new_node) Recursevily call the function to compute next and random Return the new_node Complexity Time complexity: O(n) Space complexity: O(n) Code """ # Definition for a Node. class Node: def __init__(self, x, next=None, random=None): self.val = int(x) self.next = next self.random = random """ class Solution(object): visited = {} def copyRandomList(self, head): """ :type head: Node :rtype: Node """ if not head: return None if head in self.visited: return self.visited[head] new_node = Node(head.val, None, None) self.visited[head] = new_node new_node.next = self.copyRandomList(head.next) new_node.random = self.copyRandomList(head.random) return new_node
Intuition Do a hash on the value itself, but this has a flaw that different nodes can have the same value, therefore not forming a cycle. A optiomal approach is to use the slow-fast approach. One pointer jumping one node at a time, the other jumping two. If the faster points reaches the end (node.next == null), then we don’t have a cycle. When both slow and fast meets each other, we found our cycle. ...