206. Reverse Linked List

[chengchengxu15]

Given the head of a singly linked list, reverse the list, and return the reversed list.

solution: https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-tu-jie-206-fan-zhuan-lian-biao-d-zvli/

[chengchengxu15]

没做出来。。直接参考答案了。。。。

[chengchengxu15]

1 solution

recursive solution:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newHead

作者：edelweisskoko 链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-tu-jie-206-fan-zhuan-lian-biao-d-zvli/

注释：

head.next.next = head

这一行是让head.next 再指回head. 比如 [1,2,3,4,5] 1.next 是 2 1.next.next = 1 就是让2 指向1

head.next = None

主要是让head.next的指向断掉。 因为之后会再把head指向到head之前的那个： 用head.next.next = head

[chengchengxu15]

2 solution

iterative solution

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre,cur = None,head
        while cur:
            tmp = cur.next
            cur.next =pre
            pre=cur
            cur= tmp
        return pre

https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-shuang-zhi-zhen-di-gui-yao-mo-/ 迭代需要三个指针，pre，cur，nxt，分别按顺序指向三个节点 三个指针的初始化：pre指向空节点，cur指向头结点head，nxt指向head.next 因为head.next可能不存在，nxt在循环中定义，这样如果head为空就不会进入循环 迭代过程 1 tmp指向cur.next 2 cur.next指向pre 3 pre移动到cur位置 4 cur移动到tmp位置 当cur为空时，返回pre