反转链表算法-Java

题目

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

数据范围： n\leq1000n≤1000< 要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时， 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。 以上转换过程如下图所示：

示例1

输入：{1,2,3} 返回值：{3,2,1}

示例2

输入：{} 返回值：{} 说明： 空链表则输出空

描述

这是一篇针对初学者的题解，共用2种方法解决。

• 知识点：单链表
• 难度：一星

---

正规解法

• 初始化：3个指针

1. pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr
2. cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head
3. nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存

• 接下来，循环执行以下三个操作

1. nex = cur->next, 保存作用
2. cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点
3. pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点 循环条件，当然是cur != nullptr 循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点 这里以1->2->3->4->5 举例：

/**
 * @author LaoTie
 * @project LaoTieTest
 * @date 2021/11/9
 */

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public static ListNode reverseList(ListNode head) {
  ListNode pre = null;
  ListNode cur = head;
  ListNode next = null;
  while (cur !=null){
      next = cur.next;
      cur.next= pre;
      pre = cur;
      cur = next;
  }
  return pre;
}