707.design-linked-list.md

707. Design Linked List

Singly Linked List

class Node(val data: Int) {
    var next: Node? = null
}

class MyLinkedList() {

    private var head: Node? = null
    private var size = 0

    fun get(index: Int): Int {
        if (index < 0 || index >= size) return -1
        var i = 0
        var current: Node? = head
        while (i < index) {
            current = current?.next
            i++
        }
        return current?.data ?: -1
    }

    fun addAtHead(`val`: Int) {
        val newNode = Node(`val`)
        size++
        newNode.next = head
        head = newNode
    }

    fun addAtTail(`val`: Int) {
        // Pitfall: If head is null, we need to add at head
        if (head == null) {
            addAtHead(`val`)
            return
        }
        var lastNode: Node? = head
        while (lastNode?.next != null) {
            lastNode = lastNode.next
        }
        val newNode = Node(`val`)
        lastNode?.next = newNode
        size++
    }

    fun addAtIndex(index: Int, `val`: Int) {
        if (index < 0 || index > size) return
        if (index == 0) {
            addAtHead(`val`)
        } else if (index == size) {
            addAtTail(`val`)
        } else {
            var previous: Node? = null
            var current: Node? = head
            var i = 0
            while (i < index) {
                i++
                previous = current
                current = current?.next
            }
            val newNode = Node(`val`)
            previous?.next = newNode
            newNode.next = current
            size++
        }
    }

    fun deleteAtIndex(index: Int) {
        if (index < 0 || index >= size) return
        // We always add a sentinel node to the head for deletion
        val sentinel = Node(-1)
        sentinel.next = head

        var previous: Node? = sentinel
        var current: Node? = head
        var i = 0
        while (i < index) {
            i++
            previous = current
            current = current?.next
        }
        previous?.next = current?.next
        head = sentinel.next
    }
}

Singley Linked List with Sentinel Node as Head

We use sentinel node as head, so we don't need to handle the edge case of adding at head and deleting at head.

data class Node(
    val `val`: Int,
    var next: Node? = null
)

class MyLinkedList() {

    private val sentinel = Node(-1)
    private var size = 0

    fun get(index: Int): Int {
        if (index < 0 || index >= size) return -1
        var i = 0
        var current: Node? = sentinel.next
        while (i < index) {
            current = current?.next
            i++
        }
        return current?.`val` ?: -1
    }

    fun addAtHead(`val`: Int) {
        // sentinel -> newNode
        // sentine -> newNode -> oldHead
        val head: Node? = sentinel.next
        val newNode = Node(`val`)
        newNode.next = head
        sentinel.next = newNode
        size++
    }

    fun addAtTail(`val`: Int) {
        // We start from sentinel, so we don't need to handle the edge case of adding at head (when size is zero)
        var current: Node? = sentinel
        while (current?.next != null) {
            current = current.next
        }
        val newNode = Node(`val`)
        current?.next = newNode
        size++
    }

    fun addAtIndex(index: Int, `val`: Int) {
        if (index < 0 || index > size) return
        if (index == 0) {
            addAtHead(`val`)
            return
        }
        if (index == size) {
            addAtTail(`val`)
            return
        }
        var i = 0
        var previous: Node? = sentinel
        var current: Node? = sentinel.next
        while (i < index) {
            previous = current
            current = current?.next
            i++
        }
        val newNode = Node(`val`)
        previous?.next = newNode
        newNode.next = current
        size++
    }

    fun deleteAtIndex(index: Int) {
        if (index < 0 || index >= size) return
        var previous: Node? = sentinel
        var current: Node? = sentinel.next
        var i = 0
        while (i < index) {
            previous = current
            current = current?.next
            i++
        }
        previous?.next = current?.next
        size--
    }

}

Single Linked List with Sentinel Node as Head

Without maintaining the size of the linked list.

Alway think about the two cases:

sentinel -> __  // empty linked list
sentinel -> [0] // non-empty linked list

data class MyNode(
    val `val`: Int,
    var next: MyNode? = null
)

class MyLinkedList() {

    private val sentinel = MyNode(-1)

    fun get(index: Int): Int {
        var c: MyNode? = sentinel
        var i = -1
        while (i < index) {
            c = c?.next
            i++
        }
        return c?.`val` ?: -1
    }

    fun addAtHead(`val`: Int) {
        val next = sentinel.next
        val newNode = MyNode(`val`)
        newNode.next = next
        sentinel.next = newNode
    }

    fun addAtTail(`val`: Int) {
        var c: MyNode? = sentinel
        while (c?.next != null) {
            c = c?.next
        }
        c?.next = MyNode(`val`)
    }

    fun addAtIndex(index: Int, `val`: Int) {
        var i = 0
        var prev: MyNode? = sentinel
        var current: MyNode? = sentinel.next

        while (i < index) {
            prev = current
            current = current?.next
            i++
        }

        // Ensure that the index is valid
        if (prev != null) {
            val newNode = MyNode(`val`)
            prev?.next = newNode
            newNode.next = current
        }
    }

    fun deleteAtIndex(index: Int) {
        var i = 0
        var prev: MyNode? = sentinel
        var current: MyNode? = sentinel.next

        while (i < index) {
            prev = current
            current = current?.next
            i++
        }
        prev?.next = current?.next
    }

}