[LeetCode] 经典 - ListNode 翻转

在LeetCode里面有很多题是关于ListNode翻转的。我们把核心的部分拿出来说，写成一个模板。

模板介绍

public ListNode reverse(ListNode begin, ListNode end) {
    ListNode cur = begin.next;
    ListNode next;
    ListNode newTail = cur;
    ListNode pre = begin;
    while (cur != end) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    begin.next = pre;
    newTail.next = end;
    // return begin.next; // 如果想返回新的head
    return newTail; // 如果想返回翻转后的的tail
}

LeetCode 26就是用了这个部分。

如果是翻转整个List，end == null，那么我们这部分核心代码可以变成：

public ListNode reverse(ListNode head) { // head是begin的next
    ListNode begin = new ListNode(-1);
    begin.next = head;
    ListNode cur = begin.next; 
    ListNode next;
    ListNode newTail = cur;
    ListNode pre = begin;
    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    begin.next = pre;
    newTail.next = null;
    return begin.next; // 如果想返回新的head
}

或者简练成：

public ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

相关题目

25 Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/

206 Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/