在LeetCode里面有很多題是關(guān)于ListNode翻轉(zhuǎn)的。我們把核心的部分拿出來(lái)說(shuō)袖牙，寫(xiě)成一個(gè)模板帐姻。
模板介紹
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; // 如果想返回翻轉(zhuǎn)后的的tail
}
LeetCode 26就是用了這個(gè)部分。
如果是翻轉(zhuǎn)整個(gè)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
}
或者簡(jiǎn)練成：
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;
}
相關(guān)題目
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/
