单链表反转Java版

头插法与尾插法

本文主要用头插法实现单链表的反转，开始前先简单了解一下头插法与尾插法。

头插法：

在头节点的后面进行插入操作，后一个插入进来的值，在前一个插入进来的值与头节点之间。

尾插法：

设法找到插入结点的上一个结点，总而言之，尾插法就是要使后面插入的结点在前一个插入结点和NULL值之间。

单链表反转

单链表反转又可分为带逻辑头结点反转和不带逻辑头节点的反转，区别就是反转过程中是否单独设置一个逻辑头结点，具体可见代码。

设节点类为Node:

1
public static class Node{
2
    private int data;
3
    private Node next;
4

5
    public Node(int data, Node next) {
6
        this.data = data;
7
        this.next = next;
8
    }
9

10
    public int getData() {
11
        return data;
12
    }
13

14
    public void setNext(Node next) {
15
         this.next = next;
16
    }
17

18
    public Node getNext() {
19
        return next;
20
    }
21
}

为方便阅读，之后不再调用Node的Setters/Getters函数，直接用其属性。

带逻辑头节点的反转

1
/**
2
* 输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
3
* @param head
4
* @return
5
*/
6
public static Node reverseList_head(Node head) {
7
    // 创建一个临时结点，当作头插法的逻辑头结点
8
    Node root = new Node(0, null);
9
    // 逻辑头结点点的下一个结点为空
10
    root.next = null;
11
    // 用于记录要处理的下一个结点
12
    Node next;
13
    // 当前处理的结点不为空
14
    while (head != null) {
15
        // 记录要处理的下一个结点
16
        next = head.next;
17
        // 当前结点的下一个结点指向逻辑头结点的下一个结点
18
        head.next = root.next;
19
        // 逻辑头结点的下一个结点指向当前处理的结点
20
        root.next = head;
21
        // 上面操作完成了一个结点的头插
22
        // 当前结点指向下一个要处理的结点
23
        head = next;
24
    }
25
    // 逻辑头结点的下一个结点就是返回后的头结点
26
    return root.next;
27
}

不带逻辑头节点的反转

该函数中不再有上面代码中开头创建的临时节点root。

1
/**
2
* 定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
3
* @param list
4
* @return
5
*/
6
public Node reverseList(Node list){
7
    if (list == null || list.getNext() == null) return list;
8
    // 用于记录当前处理的结点的
9
    Node curre = list;
10
    // 用于记录当前结点的前驱结点
11
    // 前驱结点开始为null，因为反转后的最后一个结点的下一个结点，即null
12
    // 也是反转链表的头结点
13
    Node pre = null;
14
    // 当前结点的下一个结点
15
    Node next = null;
16
    // 对链表进行头插法操作
17
    while (curre!=null){
18
        // 记录要处理的下一个结点
19
        next = curre.next;
20
        // 当前结点的下一个结点指向前驱结点，这样当前结点就插入到了反转链表的头部
21
        curre.next = pre;
22
        // 记录当前结点为前驱结点，完成一次头插
23
        pre = curre;
24
        // 当前结点指向下一个要处理的结点
25
        curre = next;
26
    }
27
    return pre;
28
}

再略微修改一下，可减少一次循环,本质上没区别，仅是因为最后一个结点肯定是反转后的头结点，所以省掉了最后一次循环：

1
public Node inverseLinkList(Node list){
2
    if (list == null || list.next == null) return list;
3

4
    Node pre = null;
5
    Node curre = list;
6
    Node next = null;
7

8
    while (curre.next!=null){
9
        next = curre.next;
10
        curre.next = pre;
11
        pre = curre;
12
        curre = next;
13
    }
14
    curre.next = pre;
15
    return curre;
16
}