logo头像

生活多彩,尽情享受!

单向链表反转

单向链表反转

单项链表节点结构

data next

data 域:存储数据元素信息的域。
next 域:存储直接后继位置的域,是存放节点的直接后继的地址(位置)的指针域(链域)。
data 域 + next 域:组成数据的存储映射,称为 节点

注意:

  • 链表通过每个节点的链域将线性表的 n 个节点按其逻辑顺序链接在一起的
  • 每个节点只有一个链域的链表称为 单链表

单链表节点结构

要实现单链表存储,首先是创建一个节点类,数据结构如下:

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
static class Node {
private int data;// 数据域
private Node next;// 指针域

public Node() {
}

public Node(int data) {
this.data = data;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}
}

实现链表反转的方法

  • 递归反转法
    在反转当前节点之前先反转后续节点。这样从头结点开始,层层深入直到尾节点才开始反转指针域的指向。简单地说就是从尾节点开始,逆向反转各节点的指针域指向。

    • head:前一节点的指针域(PS:前一节点的指针域指向当前节点)
    • head.getNext():是当前节点的指针域(PS:当前节点的指针域指向下一节点)
    • reHead:是反转后新链表的头节点(PS:即原来单链表的尾节点)

    Java 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public static Node reverse(Node head) {
    // head 看作是前一节点,head.getNext 是当前节点,reHead 是反转后新链表的头节点
    if (null == head || head.getNext() == null) {
    return head;// 若为空链或者当前结点在尾结点,则直接返回
    }
    // 先反转后续节点
    Node reHead = reverse(head.getNext());
    // 将当前节点的指针指向前一节点
    head.getNext().setNext(head);
    // 设置前一节点的指针域为 null
    head.setNext(null);
    // 反转后新链表的头结点
    return reHead;
    }
  • 遍历反转法
    递归反转是从后往前逆序反转指针域的指向,而遍历反转法是从前往后反转各个节点的指针域的指向。
    基本思路是:将当前节点 cur 的下一个节点缓存到临时节点 tmp 后,然后更改当前节点指向上一节点 pre。也就是说在反转当前节点指针指向前,先把当前节点的指针域用 tmp 临时保存,以便下次使用。

    • pre:上一节点
    • cur:当前节点
    • tmp:临时节点,用于保存当前节点的指针域

    Java 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public static Node reverse2(Node head) {
    if (null == head) {
    return head;
    }
    Node pre = head;// 上一节点
    Node cur = head.getNext();// 当前节点
    Node tmp;// 临时节点,用于保存当前节点的指针域(即下一节点)
    while (null != cur) {// 当前节点为 null,说明位于尾节点
    tmp = cur.getNext();
    cur.setNext(head);// 反转指针域的指向

    // 指针往下移动
    pre = cur;
    cur = tmp;
    }
    // 最后将原链表的头结点的指针域置为 null,还回新链表的头结点,即原链表的尾节点
    head.setNext(null);
    return pre;
    }