【linked list】Leetcode 206: Reverse Linked List

https://leetcode.com/problems/reverse-linked-list

首先要注意的几个问题：

• linked list的node只保存了一个指针，在反序的过程中，将某个node指向了它之前的node，就会丢失它之后的node的地址，所以要注意保存下来。
• edge case: 当 head = null 的情况，代码会报错，无法返回正确值，办法是直接返回null。

思路：
记录previous, current, next 的地址，以解决单向链表无法获取node前一个node的地址的问题；

步骤：

1. 将 current.next 指向prev，此时链表中间断开
2. 将 previous, current, next 都向后移一位，直到到达末尾 next = null 时，终止操作，返回链表的最后一个node的地址（也就是current）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return head;
        ListNode prev = null, cur = head, next = cur.next;
        while(true) {
            cur.next = prev;
            if(next == null)
                break;
            prev = cur;
            cur = next;
            next = cur.next;
        }
        return cur;
        
    }
}

参考：https://youtu.be/TSDl7sRxWdU

也可以用递归，参考 https://youtu.be/4mm39dVLlZ0