206-反转链表

标签：递归链表

题目信息

题目内容：

javascript

给你单链表的头节点head，请你反转链表，并返回反转后的链表。

示例 1：

rev1ex1

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

rev1ex2

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

javascript

提示：

    链表中节点的数目范围是 [0, 5000]
    -5000 <= Node.val <= 5000

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

题解

解法一

思路：

使用双指针思路，定义prev指针默认为null，cur指针默认指向head，遍历链表，然后确定cur和prev直接的指向关系，然后向右移动两个指针，直到cur === null的时候结束
temp的存在是因为我们将cur.next指向prev后，向右移动cur时，会找不到需要移动的位置，所以需要现将cur在原始链表中的next暂时记录下来，每次循环temp的值都会改变
赋值的顺序为：
1、先声明temp = cur.next，保存临时变量，也就是cur.next初始指向的节点
2、将cur.next指向prev，反转cur.next的指向
3、prev赋值为cur(prev = cur)，将prev右移一位
4、将cur赋值为temp，将cur右移一位
5、当cur为null时，遍历结束
最终的反转结果就是绿色箭头所展现的，图示如下:

双指针

代码实现：

javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let curNode = head
    let prevNode = null
    while(curNode !== null) {
        const tempNode = curNode.next
        curNode.next = prevNode
        prevNode = curNode
        curNode = tempNode
    }
    return prevNode
};

解法二

思路：

使用递归写法，可以参照上面的双指针写法来，就很容易理解

代码实现：

javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    const reverseLinklist = (prev, cur) => {
        if(cur === null) return prev
        const temp = cur.next
        cur.next = prev
        /**
         下面reverseLinklist函数的传参就相当于方法一中的这两行代码
         prevNode = curNode
         curNode = tempNode
         */
        return reverseLinklist(cur, temp)
    }
    return reverseLinklist(null, head)
};

206-反转链表 #

题目信息 #

题解 #

解法一 #

解法二 #

206-反转链表

题目信息

题解

解法一

解法二