[数据结构与算法]leetcode-链表-【双指针、递归反转、迭代反转、前序遍历、后续遍历判断回文】

双指针

2022年10月19日 17点49分

21. 合并两个有序链表
重点：

1. 使用虚拟头结点，方便返回链表（同时避免空指针的情况）
2. 使用滑动指针，方便构建链表
3. 循环需要判断结点是否为空，为空停止循环

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 虚拟头结点
        dummy = ListNode()
        p = dummy
        p1 = list1
        p2 = list2
        while p1 and p2:
            if p1.val > p2.val:
                p.next = p2
                p2 = p2.next
            else:
                p.next = p1
                p1 = p1.next
            p = p.next
        if p1:
            p.next = p1
        if p2:
            p.next = p2
        return dummy.next

86. 分隔链表
重点：

1. 跟上一题一样，有几个链表就要构造几个dummy（头结点），几个滑动指针
2. 这题需要注意 断开原链表中的每个节点的 next 指针

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        dummy1 = ListNode()
        dummy2 = ListNode()
        p1 = dummy1
        p2 = dummy2
        p = head
        while p:
            if p.val >= x:
                p2.next = p
                p2 = p2.next
            else:
                p1.next = p
                p1 = p1.next
            // 断开原链表中的每个节点的 next 指针
            temp = p.next
            p.next = None
            p = temp
        p1.next = dummy2.next
        return dummy1.next

2022年10月20日 10点14分

23. 合并K个升序链表
知识点：最小堆
练习：python构造最小堆

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

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        x = self.findFromEnd(dummy,n+1)
        x.next = x.next.next
        return dummy.next
    def findFromEnd(self,head:ListNode,k:int) -> ListNode:
        p1 = head
        p2 = head
        for i in range(k):
            p1 =  p1.next
        while p1:
            p2 = p2.next
            p1 = p1.next
        return p2

876. 链表的中间结点
知识点：快慢指针
注意点：空结点判断

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

判断链表是否包含环

boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

计算环起点

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    // 重新指向头结点
    slow = head;
    // 快慢指针同步前进，相交点就是环起点
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

链表的前序、后序遍历

二叉树的三种遍历

void traverse(TreeNode root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
}

链表兼具递归结构，树结构不过是链表的衍生。
那么，链表其实也可以有前序遍历和后序遍历

void traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}

倒序打印链表

/* 倒序打印单链表中的元素值 */
void traverse(ListNode head) {
    if (head == null) return;
    traverse(head.next);
    // 后序遍历代码
    print(head.val);
}