Leetcode: Linked List Basics

Linked lists are one of the most common data structures asked in interviews after arrays. The following problems are discussed here.

1. Delete a given node
2. Reverse list
3. Detect cycle
4. Remove nodes with given value

Delete Node in a Linked List | LeetCode OJ

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 = None
class 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

Reverse Linked List | LeetCode OJ

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

1. point each node to its previous node
2. keep the next node in another variable to move forward
3. 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

Linked List Cycle | LeetCode OJ

Detecting cycle can be done using 2 pointers.

1. Move the first pointer by 1 step
2. Move the second pointer by 2 steps
3. If there is a cycle they will meet eventually, make a check for that
4. 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

Remove Linked List Elements | LeetCode OJ

Here we need to remove nodes with a particular val in them.

1. While head contains the value shift the head
2. Check for next node having the value and delete it if it does

A better solution is

1. Make a temporary head and point it to given head
2. 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