206. 反转链表

[funnycoderstar]

题目描述

反转一个单链表。

示例:

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

解题思路

1. 使用迭代：

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用。

解题方法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prevNode = null; // 前指针节点
    //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
    while(head != null) {
        let tempNode = head.next; //临时节点，暂存当前节点的下一节点，用于后移
        head.next = prevNode; //将当前节点指向它前面的节点
        prevNode = head; //前指针后移
        head = tempNode;  //当前指针后移
    }
    return prevNode;
 };

复杂度分析

• 时间复杂度：O(n)，假设 nn 是列表的长度，时间复杂度是 O(n)。
• 空间复杂度：O(1)。

2. 使用递归：

明确递归函数的定义，reverseList的函数定义是：输入一个节点head, 以head为起点的链表反转，并返回反转之后的头部节点

解题方法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
     if(head === null || head.next === null) {
        return head;
    }
    // 在这里进行递归，用 last 来接收反转之后的头节点
    const last = reverseList(head.next);
    head.next.next = head;
    // 反转之后，之前的 head变成了最后一个节点，链表的末尾要指向null
    head.next = null;
    return last;

   };

复杂度分析

• 时间复杂度：O(n)，假设 nn 是列表的长度，时间复杂度是 O(n)。
• 空间复杂度：O(n)。

参考

官方题解