面试高频手撕题 | 08.反转一个链表

一、知识点

链表是一种常见的数据结构，由一系列节点组成，每个节点包含两部分：数据和指针。指针指向下一个节点，从而形成链表。

反转链表是指将链表中的节点顺序倒过来，使得原来的尾节点变成头节点，原来的头节点变成尾节点。

在反转链表的过程中，需要注意以下几点：

1. 链表的反转并不会改变节点的数据，只是改变了节点之间的指针指向。
2. 反转链表可以使用迭代法或递归法。
3. 在迭代法中，需要使用三个指针来记录当前节点、前一个节点和下一个节点。
4. 在递归法中，需要注意递归的边界条件和返回值。

二、思路分析

1. 迭代法：

   • 初始化三个指针：当前节点 cur、前一个节点 prev 和下一个节点 next。
   • 将 prev 和 next 指向头节点，将 cur 指向头节点的下一个节点。
   • 循环直到 cur 为空，每次将 prev 的 next 指向 cur，将 cur 指向 prev，然后将 prev 和 next 向后移动一位。
   • 返回 prev，即为反转后的头节点。

2. 递归法：

   • 递归的边界条件是当节点为空时，返回 null。
   • 在递归函数中，将当前节点的下一个节点作为新的头节点，然后递归调用自身，直到节点为空。
   • 返回新的头节点，即为反转后的链表。

三、JavaScript 解答

1. 迭代法：

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

2. 递归法：

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

四、Java 解答

1. 迭代法：

public class ReverseLinkedList {
 public static ListNode reverseList(ListNode head) {
 ListNode prev = null;
 ListNode curr = head;
 while (curr != null) {
 ListNode next = curr.next;
 curr.next = prev;
 prev = curr;
 curr =