LeetCode-206 反转链表

💬 描述

反转一个单链表。 示例 1:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

📋 代码1 - 迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
		
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

复杂度： 时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。 空间复杂度：O(1)。

📋 代码2 - 递归

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

复杂度： 时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。 空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。

💡 思路

迭代： 要反转链表，实际上就是要反转所有相邻节点之间的指针。如代码所示，我们先定义3个指针，cur指向head, tmp指向它的下一个节点，pre指向它的上一个节点。然后进入循环。 在循环中，先找到下一个节点赋值给tmp，防止反转后丢失后续的节点。再把cur的next指向前一个节点（反转）。再进行一次右移：pre移到cur处，cur移到tmp处。 此时，头结点（pre节点）从链表中独立了出来，cur指向了第二个节点。在第二轮循环中，通过 cur.next = pre，把原来的头结点链到第二个节点之后。这就实现了前2个节点的反转。继续循环... 最终，pre会指到最后一个节点处。返回pre即可。 递归： 从后到前进行反转。具体可参照代码。下面附上力扣评论区的解读： 不妨假设链表为1，2，3，4，5。按照递归，当执行reverseList（5）的时候返回了5这个节点，reverseList(4)中的p就是5这个节点，我们看看reverseList（4）接下来执行完之后，5->next = 4, 4->next = null。这时候返回了p这个节点，也就是链表5->4->null，接下来执行reverseList（3），代码解析为4->next = 3,3->next = null，这个时候p就变成了，5->4->3->null, reverseList(2), reverseList(1)依次类推，p就是:5->4->3->2->1->null