Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Solution
超简单的解法
(Reverse-Linked-List2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /**
* 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) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
// find prev;
for(int i=1;i<m;i++)
prev = prev.next;
ListNode start = prev.next;
ListNode then = start.next;
for(int i=0;i<n-m;i++){
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
return dummy.next;
}
}
|
(Reverse-Linked-List2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
#找到m-1
mth_prev = self.findNode(dummy,m-1)
mth = mth_prev.next
# 找到n
nth = self.findNode(dummy,n)
nth_next = nth.next
nth.next = None
#revert <m,n>
self.revert(mth)
mth_prev.next = nth
mth.next = nth_next
return dummy.next
def findNode(self,head,k):
i = 0
while i<k:
if head == None:
return None
head = head.next
i += 1
return head
def revert(self, head):
prev = None
while head!=None:
nextNode = head.next
head.next = prev
prev = head
head = nextNode
return prev
|