算法-有序链表（二）反转单向链表

算法-有序链表（二）反转单向链表：

方法一：构造新链表，遍历当前链表，将数据插入新链表头部

1
2
3
4
5
6
7
8
9
public ListNode reverseList(ListNode head) {
    if (head == null)
        return null;
    ListNode n = null;
    for (; head != null; head = head.next) {
        n = new ListNode(head.val, n);
    }
    return 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
28
public ListNode reverseList(ListNode head) {
    List l1 = new List(head);
    List l2 = new List(null);
    while (true) {
        ListNode first = l1.removeFirst();
        if (first == null)
            break;
        l2.addFirst(first);
    }
    return l2.head;
}
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 h = head;
        if (head != null) {
            head = head.next;
        }
        return h;
    }
}

方法三：使用递归进行求解

1
2
3
4
5
6
7
8
9
public ListNode reList(ListNode p) {
    if (p == null || p.next == null) {
        return p;
    }
    ListNode last = reList(p.next);
    p.next.next = p;
    p.next = null;
    return last;
}

方法四：使用双指针进行逐步反转

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode reverseList(ListNode head) {
    if (head == null)
        return null;
    ListNode n1 = null;
    while (head != null) {
        ListNode o2 = head.next;
        ListNode o1 = n1;
        n1 = head;
        n1.next = o1;
        head = o2;
    }
    return n1;
}
code
#数据结构
算法-有序链表（二）反转单向链表
https://www.zheep.top/2024/12/02/算法-有序链表（二）反转单向链表/
作者
西行寺岩羊
发布于
2024年12月2日
许可协议