Java实现单向链表反转

1. 题目描述

给你一个单向链表的头节点，将这个链表反转。

例如：原链表为 1 --> 2 --> 3 --> 4，则反转后的链表为 4 --> 3 --> 2 --> 1。

2. 算法思路

我们可以让当前节点的 next 指针指向它前面的节点，由于单向链表没有指向前驱结点的指针，因此我们需要事先存储它前面的结点。在更改当前节点的 next 指针之前，还需要事先存储它后面的节点，以便在修改 next 指针之后能够继续遍历。

3. Java代码实现

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    // 单向链表反转
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = null, q = null;
        while (head != null) {
            q = head.next;
            head.next = p;
            p = head;
            head = q;
        }
        return p;
    }
}

4. 示例说明

示例一

原链表为 1 --> 2 --> 3 --> 4，执行代码：

ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;

ListNode reverseNode = new Solution().reverseList(node1);

while (reverseNode != null) {
    System.out.print(reverseNode.val + " ");
    reverseNode = reverseNode.next;
}

输出结果为：4 3 2 1

示例二

原链表为 10 --> 20 --> 30 --> 40，执行代码：

ListNode node1 = new ListNode(10);
ListNode node2 = new ListNode(20);
ListNode node3 = new ListNode(30);
ListNode node4 = new ListNode(40);

node1.next = node2;
node2.next = node3;
node3.next = node4;

ListNode reverseNode = new Solution().reverseList(node1);

while (reverseNode != null) {
    System.out.print(reverseNode.val + " ");
    reverseNode = reverseNode.next;
}

输出结果为：40 30 20 10