Reverse Linked List

发表于 | 分类于
本篇文章将介绍：使用两个指针 pre、next，循环链表将当前节点的 next 指向 pre，时间复杂度 O(n)。

胜者先胜而后求战，败者先站而后求胜

反转链表

进入 Leet Code 查看题目：https://leetcode-cn.com/problems/reverse-linked-list/

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
/**
 * 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) {
        ...
    }
}

分析

可以发现反转链表其实就是将当前节点指向上一个节点。用 pre 变量来接收上一个节点，再把当前节点的 next 设为 pre 即可。 进入 Leet Code 查看：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-die-dai-tu-jie-by-ma-rxck/

图解

反转链表.gif

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
 
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode newCur = cur.next;
            cur.next = pre;
            pre = cur;
            cur = newCur;
        }
        return pre;
    }
}