Promoted
Promoted

Linked List using pointers

Linked List Cycle II

0heading

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

0paragraph
def detectCycle(head): #Assign the head to slow and fast pointers slow = fast = head #Run a loop untill fast and next node of fast is NULL while fast and fast.next: #Move slow by one node and fast by two nodes slow = slow.next fast = fast.next.next #if they are we found cycle. so break loop if slow == fast: break else: #no cycle found return None #move head to towards start of cycle while head != slow: slow = slow.next head = head.next return head
0code

Odd Even Linked List

0heading

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is considered odd, and the second node is even, and so on.

0paragraph
def oddEvenList(head): #Create dummy1 and odd with empty node dummy1 = odd = Node(0) #Create dummy2 and even with empty node dummy2 = even = Node(0) #Traverse through head untill it is NULL while head: #assign head to next node of odd odd.next = head #assign next node of head to next node of even even.next = head.next #move odd pointer by 1 odd = odd.next #move even pointer by 1 even = even.next #move head by 2 if even is present else NULL head = head.next.next if even else None #assign even linked list to next node of odd odd.next = dummy2.next return dummy1.next #return odd
0code

Palindrome Linked List

0heading

Given the head of a singly linked list, return true if it is a palindrome.

0paragraph
def isPalindrome(head): # rev records the first half, #need to set the same structure as fast, slow, hence later we have rev.next rev = None # initially slow and fast are the same, #starting from head slow = fast = head while fast and fast.next: # fast traverses faster and moves to the end #of the list if the length is odd fast = fast.next.next # take it as a tuple being assigned #(rev, rev.next, slow) = (slow, rev, slow.next), #hence the re-assignment of slow would not affect rev (rev = slow) rev, rev.next, slow = slow, rev, slow.next if fast: #fast is at the end, move slow one step #further for comparison(cross middle one) slow = slow.next #compare the reversed first half with the second half while rev and rev.val == slow.val: slow = slow.next rev = rev.next #if equivalent then rev become None, #return True; otherwise return False return not rev
0code

Reorder List

0heading

Reorder L0 → L1 → … → Ln - 1 → Ln to L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … form

0paragraph
def reorderList(head): #if head is NULL return NULL if not head: return #Assign head yo fast and slow pointers fast = slow = head #Move fast by 2 nodes and slow by one nodes #untill fast and fast.next reach NULL while fast and fast.next: slow = slow.next fast = fast.next.next #Create pointer prev and assign it to NULL prev = None #Copy slow pointer to curr pointer curr = slow #While curr is not NULL reverse from curr while curr: next = curr.next curr.next = prev prev = curr curr = next #Copy head to first pointer and prev to second first = head second = prev #While traversing with second pointer start weaving #first and second pointers. while second.next: temp = first.next first.next = second first = temp temp = second.next second.next = first second = temp return head
0code

Add Two Numbers

0heading

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

0paragraph
def addTwoNumbers(l1, l2): #use closure and recursion def addNumbers(l1, l2, c=0): #add heads of l1, l2 and carry val = l1.val + l2.val + c c = val // 10 #calculate tens place ret = Node(val = val % 10) #take units place #check if there is value in next node of l1 or l2 or carry if l1.next or l2.next or c != 0: #if next of l1 is NULL make it empty Node if not l1.next: l1.next = Node(val=0) #if next of l2 is NULL make it empty Node if not l2.next: l2.next = Node(val=0) #call recursive to add next nodes ret.next = addNumbers(l1.next, l2.next, c) #return current node result return ret #call closure function return addNumbers(l1, l2, c=0)
0code