Promoted
Promoted
Linked List using pointers
Topic: Data Structure
Linked List Cycle II | 0 | heading |
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. | 0 | paragraph |
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 | 0 | code |
Odd Even Linked List | 0 | heading |
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. | 0 | paragraph |
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 | 0 | code |
Palindrome Linked List | 0 | heading |
Given the head of a singly linked list, return true if it is a palindrome. | 0 | paragraph |
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 | 0 | code |
Reorder List | 0 | heading |
Reorder L0 → L1 → … → Ln - 1 → Ln to L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … form | 0 | paragraph |
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 | 0 | code |
Add Two Numbers | 0 | heading |
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. | 0 | paragraph |
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) | 0 | code |