反转链表（206）

题目

反转一个单链表。

示例

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

进阶

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

算法

迭代

声明一个头节点listHead，然后依次向后遍历原链表，将当前节点插入到listHead和listHead.next之前，最后返回listHead.next

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const reverseList = (head) => {
	let listHead = new ListNode();
	while (head) {
		let nextNode = head.next;
		head.next = listHead.next;
		listHead.next = head;
		head = nextNode;
	}
	return listHead.next;
};

递归

每一次递归都将下一个节点传入reverseList(head.next)，当当前节点head等于null（为了判断是否是空链表）或者当前节点的下一个节点为null时，结束递归

对于任意一个节点，我们首先能拿到上一次递归返回的节点node，我们希望当前节点head的下一个节点指向当前节点head，所以将当前节点head赋值给head.next.next

此时head.next的指向需要被改变，因为上一步已经将head.next的next指向了当前节点head，如果此时head的next还是指向下一个节点就会造成死循环，所以我们将head的下一个指向null

最后完成当前节点head的操作后我们返回节点node，这里的node始终上一次递归返回的node，所以node没有发生变化，一直是最深一次递归返回的head，所以最后结束函数返回的就是原链表的尾节点（翻转后链表的头节点）

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const reverseList = (head) => {
	if (head === null || head.next === null) {
		return head;
	}
	let node = reverseList(head.next);
	head.next.next = head;
	head.next = null;
	return node;
};

双指针

维护两个相邻的指针，快指针是prev（默认指向head），慢指针是cur（默认指向null），将prev.next指向cur（即每次都翻转prev和cur之间的指向关系），然后都向后移动一位并重复之前的翻转，最后当prev指向null时返回cur

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const reverseList = (head) => {
	let prev = head,
		cur = null;
	while (prev) {
		let nextNode = prev.next;
		prev.next = cur;
		cur = prev;
		prev = nextNode;
	}
	return cur;
};

双指针II

有两个指针start和toEnd，开始都指向头节点head，start表示每一次操作后的链表的头部（最后返回的也是这个链表头），toEnd最后会指向null，每一次操作重复下面的过程：

• 将toEnd.next指向的节点指向start
• 将toEnd.next指向（上述改变前的）toEnd.next.next
• 将start指向（上述改变前的）toEnd.next

最后当toEnd指向null时返回start

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const reverseList = (head) => {
	if (!head) return null;
	let toEnd = head,
		start = head;
	while (toEnd.next) {
		let nextNode = toEnd.next;
		toEnd.next = toEnd.next.next;
		nextNode.next = start;
		start = nextNode;
	}
	return start;
};