BM2 链表内指定区间反转
链表内指定区间反转
http://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
- 问题不要看的太复杂,首先要看到ListNode这个类,没有构造方法,那么取出节点放到集合,反转集合再拼接节点的思路就行不通了
- 既然这样那么不如直接将链表需要反转的节点的值取出放到stack 里面,然后依次弹出,改变原链表节点的值,即可。
public ListNode reverseBetween (ListNode head, int m, int n) {
//m = n 不需要改动
if(m == n){
return head;
}
ListNode old = head;
//定义栈存放需要反转的节点值
Stack<Integer> arr = new Stack();
//第一遍遍历 取出需要交换节点的值
int index = 1;
while(head!=null){
if(index >= m && index<=n){
arr.push(head.val);
}
index++;
head = head.next;
}
ListNode temp = old;
//第二遍遍历, 将值交换
index = 1;
while(temp!=null){
if(index >= m && index<=n){
temp.val = arr.pop();
}
index++;
temp = temp.next;
}
return old;
}