🥉206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

题解

迭代

迭代还是很容易理解的，就是设置一个prev，然后交换即可

next = cur.next
cur.next = prev
prev = cur
cur = next

JavaScript

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr) {
          // 交换 
        const next = curr.next;
        curr.next = prev;
        prev = curr;
          // 往下一个节点走
        curr = next;
    }
    return prev;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        pre=None
        cur = head
        while cur:
            next=cur.next
            cur.next=pre
            pre=cur
            cur=next
        return pre

递归

可能有点不好理解，慢慢理解吧

• 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作ret
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的next指针指向当前节点
• 同时让当前结点的next指针指向NULL ，从而实现从链表尾部开始的局部反转
• 当递归函数全部出栈后，链表反转完成

var reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;
    }
    const newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};