問題描述
給定一個鏈表公黑，要求翻轉(zhuǎn)其中從m到n位上的節(jié)點邑商，返回新的頭結(jié)點。
Example
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
分析
這題解法比較直接人断，可以定義一個fakeNode, 首先拼接 1 到 m - 1的節(jié)點， 然后拼接鏈表 m 到 n reverse 之后的結(jié)果含鳞，最后拼接剩下的節(jié)點影锈。reverse鏈表這里主要使用stack和3指針方法蝉绷。
解法
方法1. Stack
ListNode fakeHead = new ListNode(0);
ListNode cur =fakeHead;
ListNode curH = head;
int cnt = n - m + 1;
//鏈接 1到m - 1節(jié)點
while(m > 1){
cur.next = curH;
curH = curH.next;
cur = cur.next;
m--;
}
cur.next = null;
//鏈接m 到 n 翻轉(zhuǎn)之后的結(jié)果
Stack<ListNode> stack =new Stack();
for(int i = 0; i < cnt; i++){
stack.push(curH);
curH = curH.next;
}
while(!stack.isEmpty()){
cur.next = stack.pop();
cur = cur.next;
}
//鏈接 n + 1 之后的鏈表
cur.next = curH;
return fakeHead.next;
時間復(fù)雜度O(n)，空間復(fù)雜度O(n)
方法2. 3指針
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode fakeHead = new ListNode(0);
ListNode cur =fakeHead;
ListNode curH = head;
int cnt = n - m + 1;
//鏈接 1到m - 1節(jié)點
while(m > 1){
cur.next = curH;
curH = curH.next;
cur = cur.next;
m--;
}
cur.next = null;
//鏈接m 到 n 翻轉(zhuǎn)之后的結(jié)果
ListNode pre = null;
ListNode next = curH.next;
ListNode tail =curH;
for(int i = 0; i < cnt; i++){
curH.next = pre;
pre = curH;
curH = next;
if(next != null){
next = next.next;
}
}
cur.next = pre;
//鏈接 n + 1 之后的鏈表
tail.next = curH;
return fakeHead.next;
}
時間復(fù)雜度O(n)熔吗，空間復(fù)雜度O(1)
