Table of Contents generated with DocToc

Sepcifically, a singly linked list is a data structure that contains a sequence of nodes such that each node contains an object and a reference to the next node in the list.

A list is similar to an array in that it contains objects in a linear order.

数组在内存中存储的方式是连续的,所以数组可以通过地址偏移量的方式,很快的定位到元素。而链表在内存中存储的方式是离散的。

因为数组是连续存储,需要足够的连续内存空间。而链表节点之间通过指针连接,可以在任意不连续的内存空间进行存储。

Linked lists boot camp

Two type:

  1. Implement your own list
  2. exploit the standard list library

Implementing a basic list APl-search, insert, delete-for singly linked lists is an excellent way to become comfortable with lists.

def ListNode():
    def __init__(self, data=0, next_node=None):
        self.data = data
        self.next = next_node

class ListNode():
    def __init__(self, data=0, next_node=None):
        self.data = data
        self.next = next_node

    # search for a key
    def search_list(node,key):
        while node and node.data != key:
            node = node.next
        return node

    # insert new_node after node.
    def insert(node, new_node):
        new_node.next = node.next
        node.next = new_node

    # delect the node past this node. Assume node is not a tail.
    def delect_after(node):
        node.next = node.next.next

Tips

237. 删除链表中的节点

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。现有一个链表 – head = [4,5,1,9],它可以表示为:

输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/delete-node-in-a-linked-list

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val, node.next = node.next.val, node.next.next

node 本身就是链表的一部分。将下一个值赋值给自己,自己指向下一个的下一个。

时间和空间复杂度都是:O(1)。

206. 反转链表

迭代

在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用!

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre
                
        '''
        p, rev = head, None
        while p:
            rev, rev.next, p = p, rev, p.next
        return rev
        '''

复杂度分析

时间复杂度:O(n),假设n是列表的长度 空间复杂度:O(1)。

递归

希望 n_k+1 的 next 指 向n_k,而 n_k.next 其实就是 n_k+1.next。所以就是n_k.next.next = n_k。最后 n_k 的 next 指向空。

// 递归
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

//尾递归
public ListNode reverseList(ListNode head) {
    return reverse(null,head);
}

private static ListNode reverse(ListNode pre,ListNode cur){
    if(cur==null) return pre;
    ListNode next = cur.next;
    cur.next = pre;
    return reverse(cur,next);
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None: return head
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return p

参考:

141. 判断链表是否有环

来源:https://leetcode-cn.com/problems/linked-list-cycle/

快慢指针

快慢指针,相交代表有环。类比龟兔赛跑。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow, fast = head, head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 判断语言必须在走了之后,在前面,第一次会一定相等的
            if slow == fast:
                return True
        return False

(时间复杂度分析有点复杂)

哈希

另外还可以用哈希表记录已经访问的节点,如果再次访问同一节点,即有环,空间复杂度为O(n)。

def hasCycle(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    visited = set()
    cur = head
    
    while cur:
        if cur in visited:
            return True
        visited.add(cur)
        cur = cur.next
    return False

142. 环形链表 II 环入口

快慢双指针

分两步:

  1. 找到快慢指针相遇的点
  2. 从head和相遇的点同时走,当相遇时,即为环相交点

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow:
                break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

class Solution(object):
    def getIntersect(self, head):
        tortoise = head
        hare = head

        # A fast pointer will either loop around a cycle and meet the slow
        # pointer or reach the `null` at the end of a non-cyclic list.
        while hare is not None and hare.next is not None:
            tortoise = tortoise.next
            hare = hare.next.next
            if tortoise == hare:
                return tortoise

        return None

    def detectCycle(self, head):
        if head is None:
            return None

        # If there is a cycle, the fast/slow pointers will intersect at some
        # node. Otherwise, there is no cycle, so we cannot find an enterance to
        # a cycle.
        intersect = self.getIntersect(head)
        if intersect is None:
            return None

        # To find the enterance to the cycle, we have two pointers traverse at
        # the same speed -- one from the front of the list, and the other from
        # the point of intersection.
        ptr1 = head
        ptr2 = intersect
        while ptr1 != ptr2:
            ptr1 = ptr1.next
            ptr2 = ptr2.next

        return ptr1

哈希

用哈希表记录已经访问的节点,如果再次访问同一节点,该节点即是环入口。

时间,空间复杂度均为O(n)。

class Solution(object):
    def detectCycle(self, head):
        visited = set()

        node = head
        while node is not None:
            if node in visited:
                return node
            else:
                visited.add(node)
                node = node.next

        return None

160. 相交链表(两个链表交点)

链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

A和B要从距离末尾同等距离的位置开始遍历,才能相交。这个位置是较短链表的头结点位置。所以需要消除A和B的长度差。

  1. 指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历
  2. 如果 pA 到了末尾,则 pA = headB 继续遍历
  3. 如果 pB 到了末尾,则 pB = headA 继续遍历
  4. 比较长的链表指针指向较短链表head时,长度差就消除了
  5. 如此,只需要将最短链表遍历两次即可找到位置

想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11},相交于结点 9。 由于 B.length (=4) < A.length (=6),pB 比pA 少经过2 个结点,会先到达尾部。将pB 重定向到 A 的头结点,pA 重定向到 B 的头结点后,pB 要比pA 多走 2 个结点。因此,它们会同时到达交点。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

时间复杂度 :O(m+n)。 空间复杂度 :(1)。

哈希表

遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点bi 是否在哈希表中。若在,则bi为相交结点。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        visited = set()
        
        ha = headA
        while ha:
            visited.add(ha)
            ha = ha.next
        
        hb = headB
        while hb:
            if hb in visited:
                return hb
            hb = hb.next
        return None

复杂度分析

时间复杂度 :O(m+n)。 空间复杂度 :O(m) 或O(n)。

21. 合并两个有序链表

链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/

递归

我们可以如下递归地定义在两个链表里的 merge 操作(忽略边界情况,比如空链表等):

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l2.next, l1)
            return l2

复杂度分析

时间复杂度:O(n+m)。 因为每次调用递归都会去掉 l1 或者 l2 的头元素(直到至少有一个链表为空),函数 mergeTwoList 中只会遍历每个元素一次。所以,时间复杂度与合并后的链表长度为线性关系。

空间复杂度:O(n+m)。调用 mergeTwoLists 退出时 l1 和 l2 中每个元素都一定已经被遍历过了,所以n+m 个栈帧会消耗O(n+m) 的空间。

链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/

迭代

A better approach, in terms of time complexity, is to traverse the two lists, always choosing the node containing the smaller key to continue traversing from.

Aug-27-2019_11-18-28-0c3ad7cb-623c-474b-8977-49207dbf83f8.mp4

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy_head = tail = ListNode(-1)
        while l1 and l2:
            if l1.val < l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next # 记得tail要往下走
        tail.next = l1 or l2 # 把剩余不为空的加进去
        return dummy_head.next

复杂度分析

时间复杂度:O(n+m) 。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, while 循环的次数等于两个链表的总长度。所有其他工作都是常数级别的,所以总的时间复杂度是线性的。

空间复杂度:O(1) 。迭代的过程只会产生几个指针,所以它所需要的空间是常数级别的。

23. 合并K个有序列表 ✨

优先队列

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

算法

通过使用PriorityQueue,降低选择最小值的时间复杂度。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from Queue import PriorityQueue

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        head = ListNode(-1)
        dummy_head = head
        
        q = PriorityQueue()
        
        for l in lists:
            if l:
                q.put((l.val, l))
        
        while not q.empty():
            val, node = q.get()
        
            head.next = ListNode(val)
            head = head.next
            
            node = node.next
            if node:
                q.put((node.val, node))
        
        return dummy_head.next

归并

234. 回文链表

链接:https://leetcode-cn.com/problems/palindrome-linked-list/solution/xing-shu-ji-jian-kuai-man-zhi-zhen-fan-zhuan-lian-/

思路

代码

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow,fast,prev = head,head,None
        while fast is not None:
            slow = slow.next
            fast = fast.next.next if fast.next is not None else fast.next
        while slow is not None:
            slow.next, slow, prev= prev, slow.next, slow
        while head and prev:
            if head.val != prev.val:
                return False
            head = head.next
            prev = prev.next
        return True

作者:jimmy00745 链接:https://leetcode-cn.com/problems/palindrome-linked-list/solution/xing-shu-ji-jian-kuai-man-zhi-zhen-fan-zhuan-lian-/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

328. 奇偶链表

四个指针,拆分为奇链表和偶链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or head.next == None: return head
        
        oddHead, evenHead, odd, even = head, head.next, head, head.next
        
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        
        odd.next = evenHead
        
        return oddHead

复杂度分析

时间复杂度:O(n) 。总共有n 个节点,我们每个遍历一次。

空间复杂度:O(1) 。我们只需要 4 个指针。

链接:https://leetcode-cn.com/problems/odd-even-linked-list/solution/qi-ou-lian-biao-by-leetcode/

19. 删除链表的倒数第N个节点

双指针

链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        s, f = dummy,dummy
        
        for i in range(n+1):
            f = f.next
        
        while f:
            s, f = s.next, f.next
        
        s.next = s.next.next
        return dummy.next

时间复杂度:O(n)

空间复杂度:O(1)

拷贝带随机指针的链表

删除链表中重复的数

总结

其他参考: