两种常见的反转链表方式

Leetcode

Publish Date: 2021-06-15

Update Date: 2021-06-19

不考虑收尾元素的反转

反转链表

题解

class Solution:
    def ReverseList(self, pHead):
        pre = None
        cur = pHead
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur  = temp
        return pre

过程解析

process 1

process 2

process 3

考虑首位元素的反转

链表内指定区间反转

题解

class Solution:
    def reverseBetween(self , head , m , n ):
        if not head or not head.next:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        start = head
        
        for _ in range(m - 1):
            pre = pre.next
            start = start.next
        
        for i in range(n - m):
            nxt = start.next
            start.next = nxt.next
            nxt.next = pre.next
            pre.next = nxt
            
        return dummy.next