力扣100题-链表

1.相交链表

• 描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

思路一：

• 分别设置两个指针指向两个链表的表头，同时往后遍历，一旦到达链表尾就跳到另一个链表头开始遍历。如果两个链表存在交点，两个指针到达交点时经过的路径是相等的，恰好相遇。如果两个链表不存在交点，那么就分别遍历了两个链表的长度，A和B都是null，返回null。

• 代码一：

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        A = headA
        B = headB
        while A != B:
            A = A.next if A else headB //如果A不是null就跳到next，否则跳到链表B
            B = B.next if B else headA
        return A

• 代码二：

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        A = headA
        B = headB
        while A != B:
            if A:         //简单直接的写法
                A = A.next
            else:
                A = headB
            if B:
                B = B.next
            else:
                B = headA
        return A

2.反转链表

• 描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路一：

• 从链表头开始，对链表的节点进行逐个的翻转。除了cur指向当前的指针，增加pre指向前一个节点，tmp记录下一个节点
• 代码：

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None //设置为空指针"None"
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

3.回文链表

• 描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路一：

• 申请新空间，用另一个链表存储反转后的链表，逐个遍历比较两个链表是否相同即可。在python中可以用一个新列表存储链表里的数字，然后直接与它的反转进行比较。
• 代码：

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        vals = [] //创建空列表
        cur = head
        while cur:
            vals.append(cur.val)
            cur = cur.next
        return vals == vals[::-1] 
    //列表切片操作list[start:end:step]，-1表示将 vals 列表中的元素逆序排列

思路二：

• 先使用快慢指针找到链表的中点，反转后半部分链表，同时得到原链表尾的位置，同时往中间走进行比较。
• 代码：

class Solution:
    def middleNode(self, head):
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return True
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)
        while head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True