0x3f 第26天 黑马web （145-167）hot100链表

1.回文链表

和重排链表很乱版一毛一样

先求middle 再求head2，

区别是这个是while head2

重排链表是while head2.next提前终止

while head2的目的是

1.奇：比较1 2         1 2      中间节点3不用比，自己和自己相等

2.偶    正好对半分

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        def middle(node):
            fast = slow = node
            while fast and fast.next:
                fast=fast.next.next
                slow = slow.next
            return slow
        def reverse(node):
            cur = node
            pre = None
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur =nxt
            return pre
        head1=head
        mid = middle(head1)
        head2 = reverse(mid)
        while head2:
            if head1.val != head2.val:
                return False
            head1= head1.next
            head2 = head2.next
        return True

2.合并两个有序链表：

核心思路：先建立一个dummy，但这个dummy和我之前写的都不一样

dummy = ListNode(next = head) 【已有链表，套虚拟头】已存在的链表

本题：

dummy = ListNode()本题是「合并两个链表」：是从零开始造新链表，最开始新链表是空的，没有头节点，自然没法给 dummy 指定next=head；

有了dummy后，cur = dummy = ListNode()

后面用cur来往后接链表，虽然看起来都接在cur后面，核心结论：cur 是 dummy 的分身 / 傀儡，cur 所有的操作，最终都会映射到 dummy 身上！

dummy 的核心作用：保存链表的起点，永远不丢失头节点，cur去干活

dummy 和 cur 是同一个对象的引用，操作cur.next就是操作dummy.next；

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = cur = ListNode()
        while list1 and list2:
            if list1.val > list2.val:
                cur.next = list2
                list2 = list2.next
            else:
                cur.next = list1
                list1 = list1.next
            cur = cur.next
        cur.next = list1 or list2
        return dummy.next

用dummy做固定锚点，用cur做移动指针，通过while(list1 and list2)循环，按值大小依次拼接两个链表的公共节点，直到其中一个链表遍历完毕；再利用链表的地址引用特性，通过cur.next=list1 or list2，一步把剩余的整条链表挂载到尾部；最后返回dummy.next，得到完整的合并链表。

---

第二天写的代码：

        if list1 is not None:
            cur.next = list1
        else:
            cur.next = list2
        return dummy.next

不够优雅，因为害怕如果用list1 or list2，cur选择了None怎么办

其实

        cur.next = list1 or list2

list1 or list2 的规则是 → 返回「二者中第一个不为空的内容」，如果都为空，就返回空 (None)这行代码的完整效果 = 能接有数据的，就接有数据的；如果都没数据，就接 Null，两种情况都合法、都正确、都是业务需要！

原文地址：https://blog.csdn.net/qq_56985164/article/details/156773604

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！