当前位置：网站首页>LeetCode 练习——206. 反转链表

LeetCode 练习——206. 反转链表

2022-07-05 17:22:00 【SK_Jaco】

1.题目描述

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

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

2.解题思路与代码

2.1 解题思路

这道题比较简单，但是也是面试中非常常见的一道题目。题目要求反转链表，可以暴力使用栈解答，但是这样做不够精简在面市场上是得不到分的，并且需要两次遍历。因此使用三个引用变量 pre、next、curr 来指代上一个节点、下一个节点和当前节点。开始将 curr 指向头节点并从头节点开始进行遍历，next 指向当前节点的下一个节点，然后让当前节点的 next 指向前一个节点，也就是 pre。再往后移动 pre 和 curr，使 pre 指向当前节点 curr ，当前节点 curr 后移指向 next。下面题目示例 1->2->3->4->5->NULL 进行图解：

首先 curr 指向头节点 1，pre 和 next 指向 null；
然后 next 指向 curr 的下一个节点 2；
curr 的 next 指向 pre，并且 curr 后移指向 2；
重复上面步骤，直到 curr 指向 null，此时返回 pre 指向节点，即反转后的头节点

2.2 代码

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        if (head == null) {
    
            return null;
        }
        ListNode pre = null;
        ListNode next = null;
        ListNode curr = head;
        while (curr != null) {
    
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}