問題連結在此: https://leetcode.com/problems/reverse-linked-list-ii/
題目要求: 給予一個linked list, 把其第m到第n個位子的node顛到過來.
已知 1 ≤ m ≤ n ≤ length of the list
例子: 1->2->3->4->5 , m = 2, n = 4
結果應回傳: 1->4->3->2->5我的想法:
其實我對於這種linked list problem蠻不擅長的
所以都會花很久時間去想到底要從何做起
這題其實是206. Reverse Linked List的延伸題
所以強烈建議大家先知道要怎麼解那題 再來玩這題
本來只是想在這邊稍微提一下顛倒整個linked list概念就好
沒有要特別寫如何解206
但發現這樣篇幅會過長
時間關係我目前就先寫了英文版的而已, 大家可以看一下這個連結
👉 check out Leetcode — 206. Reverse Linked List (recursive version) to know better about the idea of reversing the list!
讀到這邊的人 應該都是已經會了如何顛倒整個list的人了吧 😉
所以如果我們再把這題拆解一下
其實就沒有當初一開始看的那麼可怕了
那我們就繼續看下去 —
程式邏輯:
假設我們的input變數是 linked list的頭head 以及特定position m與 n.
這題需要我們有一個額外的dummy node, 去指著我們的head.
因為不保證回傳的答案一定是head開頭(比如當m=1時)
我們來把我們的linked list切成三塊來分開來看:
a. dummy -> head -> … -> the node before m
b. node m -> …. -> node n
(will be reversed, so later will be node n ->…-> node m)
c. the node right after n -> …. -> null
切完三塊後, 我們就可以來想我們分別要對part a, b, c來做什麼事了:
1. 首先先找到我們part a的最後一個node (等等需要去接part b的頭)
2. 把part b整個顛倒 (所以node n 是頭, node m 是尾)
3. 把 part a 尾 接 part b頭 (i.e., node n)
4. 把 part b尾 (i.e., node m) 接 part c 頭.
Below is the 0ms code beats 100%:
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head==null||head.next==null)
return head; //step 1.
int count = 1;
ListNode dummy = new ListNode(0,head);
ListNode prev = dummy;
while(count<m)
{
prev = head;
head = head.next;
count++;
} //step 2.
ListNode a_tail = prev; //part a 尾
ListNode b_tail = head; //現階段part b頭, 等等的part b 尾
prev = null; //現階段空, 等等的part b頭
ListNode cur = head; //現階段part b頭, 等等的part c頭
int total = n-m+1; //length of reverse list
for(int i=0;i<total;i++)
{
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
//step 3
a_tail.next = prev; // part a尾 接 part b頭 //step 4
b_tail.next = cur; // part b尾 接 part c頭
return dummy.next;
}
時間複雜度: O(n) ( 因為我們也就是慢慢的traverse part a, b, 跟c)
空間複雜度: O(1) ✌️
