reverse list

Posted on | Edited on | In

reverse list

今天面试反转链表竟然能写错，真的想杀了自己，每次都在关键时刻掉链子，难的能写出来，简单的缺写错。做链表题的时候，遍历的时候注意循环的条件。到底是p==null还是p.next==null ，然后考虑循环条件满足的时候，循环体中的变量有没有满足。碰到循环或者递归不要一步一步去模拟，这样没完没了。

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverse(ListNode head){
	if(head==null)return null;
	ListNode pre=null;
	ListNode cur=head;
	while(cur!=null){
		ListNode next=cur.next;
		cur.next=pre;
		pre=cur;
		cur=next;
	}
	return pre;
}

Sort List

分成两段，左右分别排序之后，可以递归进行，在融合。

最主要的是找中点的时候别忘记把前一个节点的next置为null，前一个节点怎么找，在循环的最后一轮，fast前进两步，fast==null||fast.next==null 此时slow还没前进，记录此时的节点pre，之后

pre.next=null

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
class Solution {
    public ListNode sortList(ListNode head) {
         if(head==null||head.next==null){
            return head;
        }
        ListNode mid=findMid(head);
        ListNode left=sortList(head);
        ListNode right=sortList(mid);
        return merge(left,right);
    }
        public ListNode findMid(ListNode node){
        ListNode fast=node;
        ListNode slow=node;
        ListNode p=null;
        while(fast!=null&&fast.next!=null){
            fast=fast.next;
            fast=fast.next;
            if(fast==null||fast.next==null){
                p=slow;
            }
            slow=slow.next;
        }
        p.next=null;
        return slow;
    }
    public ListNode merge(ListNode one,ListNode two){

        ListNode p=new ListNode(0);
        ListNode head=p;
        while(one!=null&&two!=null){
            if(one.val>two.val){
                head.next=two;
                two=two.next;
            }
            else{
                head.next=one;
                one=one.next;

            }
            head=head.next;

        }
        if(one==null){
            head.next=two;
        }else{
            head.next=one;
        }
        return p.next;



    }
}