Reverse Linked List

描述

Reverse a singly linked list.

分析

用三个指针 tail,p,q，紧紧相邻，不断前进，每次将p.next指向tail，将q.next指向p。

解法1 迭代

// Reverse Linked List
// Time Complexity: O(n), Space Complexity: O(1)
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode tail = null;
        ListNode p = head;
        ListNode q = p.next;

        while (q != null) {
            ListNode old = q.next;
            p.next = tail;
            q.next = p;

            tail = p;
            p = q;
            q = old;
        }
        return p;
    }
}

解法2 递归

// Reverse Linked List
// Time Complexity: O(n), Space Complexity: O(n)
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode tail = head.next;
        head.next = null;
        ListNode newHead = reverseList(tail);
        tail.next = head;
        
        return newHead;
    }
}