My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m <= 0 || n <= 0 || m > n)
return null;
else if (head.next == null || m == n)
return head;
int counter = 1;
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode temp = dummy.next;
ListNode preM = null;
ListNode M = null;
ListNode N = null;
ListNode preTemp = dummy;
while (temp != null) {
if (counter == m) {
preM = preTemp;
M = temp;
break;
}
counter++;
temp = temp.next;
preTemp = preTemp.next;
}
temp = temp.next;
ListNode tempM = M;
for (int i = m + 1; i <= n; i++) {
if (i == n)
N = temp;
ListNode p = temp.next;
temp.next = tempM;
tempM = temp;
temp = p;
}
preM.next = N;
M.next = temp;
return dummy.next;
}
public static void main(String[] args) {
Solution test = new Solution();
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
System.out.println(test.reverseBetween(n1, 1, 4));
}
}
My test result:
Paste_Image.png
這道題目一開始理解錯題意了奏甫。庸娱。真是啃爹。
然后港华，以前反轉(zhuǎn)鏈表暖璧，我都是遞歸做的嘿架。
沒想到可以直接一遍反轉(zhuǎn)挪钓，學(xué)習(xí)了河质。
dummy.next = head;
preTemp = head;
temp = head.next;
head.next = null;
while (temp != null) {
ListNode p = temp.next;
temp.next = preTemp;
preTemp = temp;
temp = p;
}
dummy.next = preTemp;
return dummy.next;
差不多就該長這個樣子。
代碼寫的還是很丑蔑歌。
下面是重點阴颖。
我發(fā)現(xiàn)，當(dāng)我使用了如下模型丐膝，
pre -> curr -> post
之后，大多數(shù)鏈表中的刪除結(jié)點钾菊，反轉(zhuǎn)操作帅矗。我都可以很順暢的寫下來！
一定要記住這個辦法煞烫。
代碼如下：
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m <= 0 || n <= 0 || m > n)
return null;
else if (head.next == null || m == n)
return head;
int count = 0;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = null;
ListNode curr = dummy;
while (curr.next != null) {
pre = curr;
curr = curr.next;
count++;
if (count == m)
break;
}
ListNode post = curr.next;
curr.next = null;
for (int i = m; i < n; i++) {
ListNode temp = post.next;
post.next = curr;
curr = post;
post = temp;
}
pre.next.next = post;
pre.next = curr;
return dummy.next;
}
}
**
總結(jié)： 反轉(zhuǎn)鏈表浑此，非遞歸，一遍過滞详。
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null)
return head;
/** assume m and n are under rules */
int counter = 0;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode curr = head;
ListNode pre = dummy;
while (curr != null) {
counter++;
if (counter == m)
break;
else {
pre = curr;
curr = curr.next;
}
}
ListNode post = curr.next;
while (post != null) {
counter++;
if (counter <= n) {
ListNode temp = post.next;
post.next = curr;
curr = post;
post = temp;
}
else
break;
}
pre.next.next = null;
if (post != null)
pre.next.next = post;
pre.next = curr;
return dummy.next;
}
}
采用了 dummy node + 反轉(zhuǎn)鏈表凛俱。不難紊馏。有點小煩。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m > n) {
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode curr = dummy.next;
int counter = 1;
ListNode pre_m = null;
while (curr != null) {
if (counter == m) {
pre_m = pre;
break;
}
pre = curr;
curr = curr.next;
counter++;
}
ListNode curr_next = curr.next;
for (int i = 0; i < n - m; i++) {
ListNode next = curr_next.next;
curr_next.next = curr;
curr = curr_next;
curr_next = next;
}
ListNode pre_m_next = pre_m.next;
pre_m.next = curr;
pre_m_next.next = curr_next;
return dummy.next;
}
}
一開始理解錯題意了蒲犬，以為要 replace,其實是reverse部分鏈表朱监。
然后有點麻煩吧。勉強多次提交做出來了原叮。赫编。
Anyway, Good luck, Richardo! --- 08/15/2016
