# 反转链表

题目要求：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

# 方式一

代码：

public ListNode reverseList(ListNode head) {

      ListNode n1 = null;

      ListNode p = head;

      while(p != null)

      {

        n1 = new ListNode(p.val, n1);

        p = p.next;

      }

      return n1;

    }

思路分析：

每次循环就将当前放到 n1 节点对象中，它的 next 是它之前的节点对象也就是从头开始遍历但是挂载的是从后到前

缺点：

• 每次遍历都需要创建一个节点然后存储下一个节点

# 方式二

与方法 1 类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点

代码：

class Solution {

    static class List

    {

        ListNode head;

        public List(ListNode head)

        {

          this.head = head;

        }

        public void addFirst(ListNode first)

        {

          first.next = head;

          head = first;

        }

        public ListNode removeFirst()

        {

          ListNode first = head;

          if(first != null)

          {

            head = first.next;

          }

          return first;

        }

    }

    public ListNode reverseList(ListNode head) {

      List list1 = new List(head);

      List list2 = new List(null);

      while(true)

      {

        ListNode first = list1.removeFirst();

        if(first == null)

        {

          break;

        }

        list2.addFirst(first);

      }

      return list2.head;

    }

}

# 方式三

使用递归

public ListNode reverseList(ListNode head) {

      if(head == null || head.next == null)

      {

        return head;

      }

      ListNode list = reverseList(head.next);

      head.next.next = head;

      head.next = null;

      return list;

    }

思路分析：

每次递归链表的下一个节点，判断结束出口是 p 的下一个节点如果等于 null 说明到尾了就开始回溯。

比如说 5 的话回溯就是 4，4 的 next 就是 5 而 5 的 next 就是 null 将 5 的 next 赋值为 4 ，就形成了倒序 5 -> 4。

当然此时的 4 的 next 还是指向了 5 节点，如果不进行处理的话就是 4 -> 5 , 5 -> 4 就造成了 死循环了。

我们需要将 每次 倒序 值指向 下一个值的时候让 当前的值 的 next 改变指向，指向 null 就不会死循环了也就是 p.next 当前节点的 next 指向 null。

所以我们每次回溯添加节点的结构如下：

5 -> 4，4 -> 3，3 -> 2，2 -> 1，1 -> null

# 方式四

从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束

1. 设置指针 o1 (旧头) ，n1 (新头) ，o2 (旧老二) ，分别指向第一，第一，第二节点

   $$\frac{n1\ \\o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

2. 将 o2 节点从链表断开，即 o1 节点指向第三节点

   $$\frac{n1\ \\o1}{o1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null, \frac{o2}{2}$$

3. o2 节点链入链表头部，即

   $$\frac{\alpha^2}{2} \rightarrow \frac{n1.o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

4. n1 指向 o2

   $$n1(2) \rightarrow n2(1) \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

5. o2 指向 o1 的下一个节点，即

   $$n1/2 \rightarrow o1/1 \rightarrow o2/3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

6. 重复以上 2 ~ 5 步，直到 o2 指向 null

7. 还应当考虑边界条件，即链表中不满两个元素时，无需走以上逻辑

代码：

public ListNode reverseList(ListNode head) {

      if(head != null)

      {

        ListNode o2 = head.next;

        ListNode n1 = head;

        while(o2 != null)

        {

          head.next = o2.next;

          o2.next = n1;

          n1 = o2;

          o2 = head.next;

        }

        return n1;

      }

      return head; 

    }

# 方式五

要点：把链表分成两部分，思路就是不断从链表 2 的头，往链表 1 的头搬移

1. n1 指向 null ，代表 新链表 一开始 没有元素，o1 指向 原链表 的 首节点

   $$\frac{n1}{null} , \rightarrow \frac{o1}{1} \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

2. 开始循环，o2 指向 原链表 此节点

   $$\frac{n1}{null} , \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

3. 搬移

   $$\frac{o1}{1} \rightarrow \frac{n1}{null} , \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

4. 指针复位

   $$\frac{n1}{1} \rightarrow null , \frac{o1\ \\o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$$

5. 重复 2 ~ 4 步

6. 当 o1 == null 时 退出循环

代码：

public ListNode reverseList(ListNode head) {

      if(head == null || head.next == null)

      {

        return head;

      }

      ListNode n1 = null;

      while(head != null)

      {

        ListNode o2 = head.next;

        head.next = n1;

        n1 = head;

        head = o2;

      }

      return n1;

    }