Leetcode 探索之链表

[toc]

链表小结

链表也是一种线性结构。链表可以分为单链表(只有next指针)和双链表(有next指针和prev指针)。一般情况下，使用头结点来表示整个链表。
链表中的元素所分配的内存不是连续的，因此必须通过next指针或prev指针进行遍历才能找到指定下标的元素，随机访问的时间复杂度为O(n)。
在某个位置插入元素，在不考虑遍历到该位置所需的时间的情况下，单链表只需改变next指针，时间复杂度为O(1)。双链表需要修改next和prev指针，时间复杂度也为O(1)。
对于删除链表中某个位置的元素，同上，单链表由于需要知道前一个结点，因此时间复杂度为O(n)。双链表由于具有prev指针，时间复杂度为O(1)。
因此，当操作只要是添加和删除时，可以考虑链表，如果以访问为主，则应考虑数组。

做题小结

链表问题在于理解起来较为抽象，建议通过在草稿纸上进行画图的方式来加深对于链表操作的理解。
链表中的判断条件要注意空指针错误，在进行任何访问之前要确保已经进行相关的检查。同时应该仔细定义循环结束的条件，防止出现无限循环。
双指针技巧。快慢指针。
在遍历链表时，可以直接使用给定的头结点，只访问时不要修改链表。当涉及到修改链表时，最好使用一个哨兵结点作为头结点，可以避免处理头结点为空的相关情况，减少思考的复杂度和出错率。
当修改链表时，不能想当然，最好是在草稿纸上模拟相关操作，看看修改指针后链表的变化，防止出现循环链表的情况。

链表相关实现

单链表

不带哨兵结点的单链表

class MyLinkedList {
    private int size;
    private ListNode head;

    /**
     * Initialize your data structure here.
     */
    MyLinkedList() {
        size = 0;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.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.
     */
    public void addAtHead(int val) {
        ListNode cur = new ListNode(val);
        cur.next = head;
        head = cur;
        size++;
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(int val) {
        if (size == 0) {
            addAtHead(val);
        }
        ListNode tmp = head;
        for (int i = 0; i < size - 1; i++) {
            tmp = tmp.next;
        }
        tmp.next = new ListNode(val);
        size++;
    }

    /**
     * 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.
     */
    public void addAtIndex(int index, int val) {
        if (index == size) {
            addAtTail(val);
        } else if (index <= 0) {
            addAtHead(val);
        } else if (index > 0 && index < size) {
            ListNode tmp = head;
            for (int i = 0; i < index - 1; i++) {
                tmp = tmp.next;
            }
            ListNode add = new ListNode(val);
            add.next = tmp.next;
            tmp.next = add;
            size++;
        }
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {
        if (index >= 0 && index < size) {
            if (index == 0) {
                head = head.next;
                size--;
            } else {
                ListNode cur = head;
                for (int i = 0; i < index; i++) {
                    cur = cur.next;
                }
                ListNode prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                prev.next = cur.next;
                size--;
            }
        }
    }
}
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

带哨兵结点的单链表

class MyLinkedList {
    private int size;
    private ListNode head;

    /**
     * Initialize your data structure here.
     */
    MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
        }
        return cur.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.
     */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(int val) {
        addAtIndex(size, 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.
     */
    public void addAtIndex(int index, int val) {
        if (index <= 0) {
            index = 0;
        } else if (index > size) return;;
        size++;
        ListNode prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        ListNode cur = new ListNode(val);
        cur.next = prev.next;
        prev.next = cur;
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {
        if (index >= 0 && index < size) {
            size--;
            ListNode prev = head;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next;
        }
    }
}

双链表

不使用伪头伪尾的双链表

不使用伪头，伪尾

class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    ListNode(int x) {
        val = x;
        next = null;
        prev = null;
    }
}

class MyLinkedList {
    int size;
    ListNode head;

    /**
     * Initialize your data structure here.
     */
    public MyLinkedList() {
        size = 0;
        head = null;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.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.
     */
    public void addAtHead(int val) {
        size++;
        ListNode cur = new ListNode(val);
        cur.next = head;
        cur.prev = null;
        if (head != null) {
            head.prev = cur;
        }
        head = cur;
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(int val) {
        if (head == null) {
            addAtHead(val);
        } else {
            ListNode pre = head;
            while (pre.next != null) {
                pre = pre.next;
            }
            size++;
            ListNode cur = new ListNode(val);
            cur.next = null;
            cur.prev = pre;
            pre.next = cur;
        }
    }

    /**
     * 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.
     */
    public void addAtIndex(int index, int val) {
        if (index <= 0) {
            addAtHead(val);
        } else if (index == size) {
            addAtTail(val);
        } else if (index < size) {
            ListNode pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            size++;
            ListNode cur = new ListNode(val);
            cur.next = pre.next;
            cur.prev = pre;
            pre.next = cur;
            cur.next.prev = cur;
        }
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {
        if (index == 0) {
            size--;
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
        } else if (index == size - 1) {
            size--;
            ListNode pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            pre.next = null;
        } else if (index > 0 && index < size - 1) {
            size--;
            ListNode pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;
            pre.next.prev = pre;
        }
    }
}

使用伪头伪尾的双链表

//使用伪头伪尾
class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    ListNode(int x) {
        val = x;
        next = null;
        prev = null;
    }
}

class MyLinkedList {
    int size;
    ListNode head;
    ListNode tail;

    /**
     * Initialize your data structure here.
     */
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        if (index + 1 < size - index) {
            for (int i = 0; i < index + 1; i++) {
                cur = cur.next;
            }
        } else {
            cur = tail;
            for (int i = 0; i < size - index; i++) {
                cur = cur.prev;
            }
        }
        return cur.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.
     */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(int val) {
        addAtIndex(size, 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.
     */
    public void addAtIndex(int index, int val) {
        if (index <= 0) {
            index = 0;
        }
        if (index <= size) {
            ListNode pre = head;
            if (index  < size - index) {
                for (int i = 0; i < index; i++) {
                    pre = pre.next;
                }
            } else {
                pre = tail;
                for (int i = 0; i < size - index + 1; i++) {
                    pre = pre.prev;
                }
            }
            ListNode cur = new ListNode(val);
            cur.next = pre.next;
            cur.prev = pre;
            cur.next.prev = cur;
            pre.next = cur;
            size++;
        }
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {
        if (index >= 0 && index < size) {
            ListNode pre = head;
            if (index < size - index) {
                for (int i = 0; i < index; i++) {
                    pre = pre.next;
                }
            } else {
                pre = tail;
                for (int i = 0; i < size - index + 1; i++) {
                    pre = pre.prev;
                }
            }
            pre.next = pre.next.next;
            pre.next.prev = pre;
            size--;
        }
    }
}

题目索引

141环形链表（easy）

快慢指针，类似跑步，快的总能追上慢的。

142环形链表2（medium）

快慢指针，注意各变量间的数量关系即可，通过画图理解。

160相交链表（easy）

设相交部分长度为c，则a+c+b = b+c+a。

要保留链表结尾的NULL，不能修改链表，否则链表被改变为循环链表，造成无限循环，应该以访问到null作为更改的标志，而不能真正修改链表。

19删除链表的倒数第N个节点（medium）

快指针快N布，若N大于链表长度，表示删除第一个结点。

206反转链表（easy）

交换，递归，迭代。

203移除链表元素（easy）

递归+迭代（哨兵结点）

328奇偶链表（medium）

234回文链表（easy）

反转后遍历

21合并两个有序链表（easy）

递归+迭代

2两数相加（medium）

模拟

430扁平化多级双向链表（medium）

转为二叉树进行遍历

138复制带随机指针的链表（medium）

DFS，使用HashMap。

61旋转链表（medium）

模拟，根据数学关系找到新的头和新的结尾。