LeetCode: 707. Design Linked List

题目¶

原题地址：https://leetcode.com/problems/design-linked-list/

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the index-th node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the index-th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the index-th node in the linked list, if the index is valid.

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]

Output
[null, null, null, null, 2, null, 3]

Explanation

MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

0 <= index, val <= 1000
Please do not use the built-in LinkedList library.
At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

解法¶

使用单向链表实现¶

实现时主要需要注意处理几个边界 case:

当链表只有一个元素时，记得确保 head 和 tail 要指向同一个节点
当链表没有元素后，记得确保 head 和 tail 都没有指向任何节点
当删除 tail 指向的节点时，记得更新 tail 指向原来节点的上一个节点

这个方法的 Python 代码类似下面这样:

class Node(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class MyLinkedList(object):

    def __init__(self):
        self._head = None
        self._tail = None
        self._length = 0


    def get(self, index):
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self._length:
            return -1
        node = self._get_node_by_index(index)
        return node.val


    def addAtHead(self, val):
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        :type val: int
        :rtype: None
        """
        node = Node(val, self._head)
        self._head = node
        self._length += 1

        # 只有一个元素的链表 head 和 tail 指向同一个节点
        if self._length == 1:
            self._tail = self._head

    def addAtTail(self, val):
        """
        Append a node of value val to the last element of the linked list.
        :type val: int
        :rtype: None
        """
        node = Node(val)
        if self._tail is not None:
            self._tail.next = node
        self._tail = node
        self._length += 1

        # 只有一个元素的链表 head 和 tail 指向同一个节点
        if self._length == 1:
            self._head = self._tail


    def addAtIndex(self, index, val):
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        :type index: int
        :type val: int
        :rtype: None
        """
        if index > self._length:
            return
        if index == 0:
            self.addAtHead(val)
            return
        if index == self._length:
            self.addAtTail(val)
            return

        pre = self._get_node_by_index(index -1)
        curr = pre.next
        node = Node(val, curr)
        pre.next = node
        self._length += 1

    def deleteAtIndex(self, index):
        """
        Delete the index-th node in the linked list, if the index is valid.
        :type index: int
        :rtype: None
        """
        if index >= self._length:
            return

        if index == 0:
            self._head = self._head.next
        else:
            pre = self._get_node_by_index(index -1)
            curr = pre.next
            pre.next = curr.next
            # 删除 tail 指向的节点时更新新的 tail 指向节点
            if index == self._length - 1:
                self._tail = pre

        self._length -= 1
        # 当链表为空时 head 和 tail 不指向任何节点
        if self._length == 0:
            self._tail = self._head = None


    def _get_node_by_index(self, index):
        node = self._head
        curr_index = 0
        while node is not None:
            if curr_index == index:
                return node
            curr_index += 1
            node = node.next

        return None


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

题目¶

解法¶

使用单向链表实现¶

Recommend

Linked List Cycle

数据结构之链表(Linked list)

LeetCode: 142. Linked List Cycle II

LeetCode: 206. Reverse Linked List

Singly Linked List: How To Insert and Print Node

How To Reverse a Singly Linked List

Singly Linked List: How To Find and Remove a Node

Building a Linked List in Python with Examples

Leetcode 114. Flatten Binary Tree to Linked List

Detecting Linked List Cycle. (LeetCode)

About Joyk