LeetCode(206)反转链表

今天要练习的题目是：力扣（LeetCode)的第206题，反转链表

题目要求

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

示例：

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

提示：

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

解题思路

关于链表和数组的题目，小呆还是优先考虑是否可以用双指针算法解决，毕竟最近刷的几道题都与双指针有关。由于链表之间是由next相连，所以反转链表其实就是把next的指向反转。那如何将next指向反转的呢？一共有3步：

1. 链表的尾部节点的next一定指向null，所以我们初始化两个指针prev，curr，让其一个指向null，一个指向链表头head
2. 进入循环，终止条件为curr !== null表示链表已经循环完毕
3. 由于反转next会断掉当前链表，所以创建一个临时变量next，指向curr.next，防止反转next找不到路
4. 将curr.next指向prev，然后将prev指向curr，最后将curr指向next
5. 最后返回prev，链接就反转完成了

老规矩一张动态gif图辅助理解代码：

/**
 * 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 prev = null, curr = head
  while(curr !== null) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }
  return prev
}

小结

其实可以发现，只要巧妙的利用已经学会的算法，稍加变通，就可以解出问题。加油加油加油！

引用

力扣LeetCode的第206题-反转链表