链表常用操作备忘

last modify

• 链表常用操作

  • 反转链表

  • 找中间节点

• 更多问题

链表常用操作

反转链表

206. 反转链表 - 力扣（LeetCode）

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # 顶针写法
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        return pre

找中间节点

876. 链表的中间结点 - 力扣（LeetCode）

根据中间节点的定义, 有两种写法; 当链表为奇数个节点时, 两者返回相同; 区别在于当链表中有偶数个节点时,

• 法1 返回后一个中间节点,

• 法2 返回前一个中间节点;

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # 法1)
        slow, fast = head, head
        # 法2)
        # slow, fast = head, head.next
        while fast and fast.next:  # 当 fast 不为 None 时, slow 永远不为 None
            slow = slow.next
            fast = fast.next.next
        
        return slow

更多问题

algorithms/链表