数据算法之反转链表（五种方法）_链表反转

题目描述：

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

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

提示代码：

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这道题来自力扣的第206题，今天我们尝试使用五种不同的方法来实现链表的反转。

1.常规思路解题

第一种方法也是最容易想到的方法，就是将我们链表中的数据通过倒序存储到一个新的链表中即可完成链表的反转。

代码示例

//定义节点类
public class ListNode {
    int val;
    ListNode next;

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

    @Override
    //重写tostring方法，方便我们的节点按照题目要求输出
    public String toString() {
        //定义一个StringBuilder可变的字符串类,
        StringBuilder str = new StringBuilder(32);
        str.append("[");
        ListNode p = this;
        while (p != null) {
            str.append(p.val);
            if (p.next != null) {
                str.append(",");
            }
            p = p.next;

        }
        str.append("]");
        return str.toString();
    }
}

class Solution {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(5, null);
        ListNode listNode2 = new ListNode(4, listNode1);
        ListNode listNode3 = new ListNode(3, listNode2);
        ListNode listNode4 = new ListNode(2, listNode3);
        ListNode listNode5 = new ListNode(1, listNode4);
        System.out.println(listNode5.toString());
        System.out.println(reverseList(listNode5).toString());
    }

    public static ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode(head.val, null);
        ListNode p = head.next;
        while (p != null) {
            //头部的一个结点保存上一节点的最后一条数据
            //而后这段代码从这一节点开始，以后的数据都在头部插入,也就是这一节点之前去插入数据
            //为什么还是用原来的节点接收数据是因为他始终是一个头部的第一个节点，只不过不断的在更新头结点
            newHead = new ListNode(p.val, newHead);
            p = p.next;

        }
        return newHead;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

在以上的方法中只要理清了逻辑理解起来还是没问题的，建议先将基础常规思路看懂，再往下继续阅读。

2. 常规思路解题方法的优化

这种方法利用到了集合的概念，在Java中LinkList维护的就是这样一个节点类，在LinkList集合中有两个方法可以完成我们的操作分别为addFirst和removeFirst方法，在这里LinkList作为容器管理节点类，一个容器执行removeFirst删除头部节点类，另一个容器执行addFirs方法将那个容器里的数据添加到这个容器里，最后成功的实现反转链表。

在这里，我们呢先用Java提供的LinkList完成这一功能

代码示例

 LinkedList list = new LinkedList();
        LinkedList list2 = new LinkedList();
        Collections.addAll(list,1,2,3,4,5);
        System.out.println(list.toString());
        while (!list.isEmpty()){
            list2.addFirst(list.removeFirst());
        };
        System.out.println(list2.toString());
    }
1
2
3
4
5
6
7
8
9

在这里我们需要自己构建一个这样的容器，当然我们不要和java中的LinkList一样，只需要实现我们要使用的addFirst和removeFirst方法即可,c

代码示例

  public static ListNode reverseList2(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;
    }

}

//定义容器类
class List {
    //定义头结点指针
    ListNode head;

    public List(ListNode head) {
        this.head = head;
    }
    public void addFirst(ListNode listNode){
        //原来的头结点向后移动
        listNode.next = head;
        //新加入的节点成为头结点
         head = listNode ;
    }
    public ListNode removeFirst(){
        //先拿到头结点。
       ListNode firt = head;
       if (firt != null){
           //头结点删除，头结点之后的节点成为新的头结点
           head = firt.next;
        }
       return firt;

    };


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

3. 递归解题方法

先来看代码：

代码示例：

public static ListNode reverseList3(ListNode head) {
        //利用递归 实现链表的反转
        //递归跳出循环的条件，应该有两个
        //当 p.next == null表明是最后一个节点,
        // 另一个是P == null，这个时候说明传入时一个空节点，也要返回Null；
        // 两个条件同时满足即可结束递归。
        if (head == null || head.next == null){
            return head;//返回最后一个节点
        }
       //等所有递结束，开始归的时候调整我们的指针
        ListNode last = reverseList3(head.next);
        //递归思路：
        //只要让每次进来的节点反转他们的指向，即可完成反转链表
        //例如 传入的节点时 4 -> 5,现在使得5 -> 4 ,
        head.next.next = head;
        head.next = null;
        //接收最后一个节点

        return last;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

递归的方法思路就是通过反转节点的指针达到反转链表的效果，在上述代码中最难理解的是这么两段段代码，

        head.next.next = head;
        head.next = null;
1
2

在这里使用图的方式向大家解读这两段代码，

首先是head.next.next = head;

在没有递归之前，我们的链表状态是这样的：

由于发生递归的代码在我们这一行代码的上面，也就是说只有找到了最后一个节点才会执行我们的这一段代码，也就是从4开始执行指针的反转。

如图所示：

最终达到了反转链表的效果。

4. 指针思想解决问题

在这种方法中我们在同一条链表中操作，不同的是我们定义了三个指针来操作我们的节点中的指针使其完成反转链表的功能。

具体实现思路：

定义指针n1用来代表调整之后的链表的头结点。

定义指针o1用来代表未调整之前的链表头结点。

定义指针o2用来代表未调整之前的链表的第二个节点。

相关指针指向如图所示：

通过不断的调整最终完成链表的反转，反转过程如下图所示：

然后重复操作即可完成所有节点指针的调整。

代码示例：

    public static ListNode reverseList4(ListNode o1) {
        //头部指针在局部变量中被定义，
        //定义指针n1,因为节点还没有调整，所以n1和o1指向相同，即：
        ListNode n1 = o1;
        //定义指针o2,指向o1指向的下一个节点即：
        ListNode o2 = o1.next;

        //当o2指向为null时说明所有节点已经调整完毕，链表已经反转
        while (o2 != null){
            //让o1的指针指向o2的指针
            o1.next = o2.next;
            //02的指针指向n1.
            o2.next = n1;
            //更新n1指针
            n1 = o2;
            //更新o2的指针
            o2 = o1.next;

        }
        return n1;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5. 指针方法另一种思路

这种方法和第二种方法是相似的，通过在一个链表中移除头节点添加到另一个链表的头部，不同的是对于第二种方法来说使用的是面向对象的思路来编写代码，在这种方法中则是使用的是面向过程的思路解决这一问题。

假设有两个链表

o1和n1是两个链表的头部节点。

o1代表的是我们旧的链表的头部节点，里面存储着我们要操作的原始数据。

n1代表着新链表，但是这个新的链表，在开始时是一个空的链表，通过不断的从旧的链表中的头部数据一个一个移除，再一个一个添加到新链表的头部，最终完成链表的反转。

一开始两个链表的状态如图：

在完成一次搬移之后的两个链表的状态如下图所示：

转化为代码为：

代码示例

public static ListNode reverseList4(ListNode o1) {
        //定义新链表头部节点：
        ListNode n1 = null;
        //当o1 = null的时候说明所有节点操作完成
        while (o1 != null){
            //将第二次循环o1 的值先取出来
            ListNode o2 = o1.next;
            //o1的指针不再指向之前的节点，而是加入新节点指向新节点的头结点
            o1.next = n1;
            //更新新链表的头结点指针n1
            n1 = o1;
            //更新旧节点的头结点
            o1 = o2;

        }
        return n1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

如果你完全理解了第四种解法，那么这种方法对你来说简直牛刀小试。