class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if head == None or head.next == None: return head pre = head cur = head.next
head.next = None while cur != None: temp = cur.next cur.next = pre pre = cur cur = temp return pre
以上代码单独考虑了特殊情况，实际上可以写在一起，直接将 pre 设置为 None，cur 设置为 head 即可。
递归法
本质上是多次完成以下任务：将当前 cur.next 赋值为 pre，然后移动 cur 和 pre。可以使用递归的方法，写一个函数来多次完成上述过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre = None cur = head return self.reserve(pre, cur)
def reserve(self, pre, cur): if cur == None: return pre temp = cur.next
class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: if head == None or head.next == None: return head dummy_head = ListNode(0, head) pre = dummy_head cur1 = head cur2 = head.next
while True: lat = cur2.next cur2.next = cur1 cur1.next = lat pre.next = cur2
if lat != None and lat.next != None: pre = cur1 cur1 = lat cur2 = lat.next else: return dummy_head.next
class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy_head = ListNode(0, head) length = 0 cur = dummy_head.next
while cur != None: length += 1 cur = cur.next
i = 0 cur = dummy_head.next pre = dummy_head while i < length - n: cur = cur.next pre = pre.next i += 1 pre.next = cur.next
return dummy_head.next
思路 2
要求只遍历一遍链表：双指针的典型应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。（假设链表长度为 l，fast 移动了 l，slow 移动了 l - n,）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy_head = ListNode(0, head) fast = dummy_head.next slow = dummy_head.next pre = dummy_head i = 0 while fast != None: if i < n: i += 1 else: slow = slow.next pre = pre.next
