Leetcode: Linked List Basics
3 min readDec 26, 2016
Linked lists are one of the most common data structures asked in interviews after arrays. The following problems are discussed here.
- Delete a given node
- Reverse list
- Detect cycle
- Remove nodes with given value
The trick here is to copy data of next node to current node and then delete the next node
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place.
"""
node.val = node.next.val
node.next = node.next.next
I have asked this question to almost everyone I have interviewed to check if they know the basic of their preferred programming language or not. There are many ways to accomplish this.
I have solved it in constant space and linear time using 3 pointers. As we iterate through the list
- point each node to its previous node
- keep the next node in another variable to move forward
- start the iteration with head and a null previous node
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
p, q, r = None, head, head.next
while r:
q.next = p
p = q
q = r
r = r.next
q.next = p
return q
Detecting cycle can be done using 2 pointers.
- Move the first pointer by 1 step
- Move the second pointer by 2 steps
- If there is a cycle they will meet eventually, make a check for that
- Otherwise second will reach end of list, exit and return false in that case
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
p = q = head
while q and q.next and q.next.next:
p = p.next
q = q.next.next
if p == q:
return True
return False
Here we need to remove nodes with a particular val in them.
- While head contains the value shift the head
- Check for next node having the value and delete it if it does
A better solution is
- Make a temporary head and point it to given head
- Check for next node having the value and delete it if it does
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if not head:
return None
while head and head.val == val:
head = head.next
p = head
while p and p.next:
if p.next.val == val:
p.next = p.next.next
else:
p = p.next
return head def removeElements(self, head, val): p = ListNode(val - 1)
p.next = head
q = p
while p.next:
if p.next.val == val:
p.next = p.next.next
else:
p = p.next
return q.next