206. 反转链表

Problem: 206. 反转链表

思路

这是一道非常经典的链表题。如果对链表的使用不熟悉，第一印象可能是开一个数组来存反转后的链表，然后再拼接起来。但是这样需要多开$O(n)$的内存。实际上，利用链表的性质，可以只用$O(1)$的内存，并且在不增加时间复杂度的情况下反转链表。

为了完成这个操作，我们需要多利用一个指针，即使用双指针。其中左指针指向已经翻转的链表的最后一个元素，右指针指向未被反转的第一个元素。

这样，我们每次只需要把右指针移向头，并相应地更改他们的next指针，然后把左指针指向右指针的下一个元素即可。

Code

/**
 * 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) {
        if (head == null) return null;
        ListNode p = head.next;
        ListNode q = head;
        while (p != null) {
            q.next = p.next;
            p.next = head;
            head = p;
            p = q.next;
        }
        return head;
    }
}