力扣Hot 100题解之链表（Python版）第一题解析

一、160. 相交链表

class ListNode:
	def __init__(self, x):
		self.val = x
		self.next = node
class Solution:
	def getIntersectionNode(self, headA, headB):
		p, q = headA, headB
		while p is not q:
			p = p.next if p else headB
			q = q.next if q else headA
		return p

二、206. 反转链表

class ListNode:
	def __init__(self, val, next):
		self.val = val
		self.next = next
class Solution:
	def reverseList(self, head):
		pre = None
		cur = head
		while cur:
			nxt = cur.next
			cur.next = pre
			pre = cur
			cur = nxt
		return pre

三、234. 回文链表

3.1. 876. 链表的中间结点

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head):
        t1 = t2 = head
        while t2 and t2.next:
            t1 = t1.next
            t2 = t2.next.next
        return t1

    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next  # 记录下一个节点
            cur.next = pre  # 头插法，上个节点作为新节点的后继
            pre = cur       # 头插法，新节点作为新的前节点
            cur = nxt
        return pre

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

作者：Y1nhl