Reorder nodelist

node 0, node n-1, node 1, node n-2……

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
public void reorderList(ListNode head) {
    if(head == null) return;

    Stack<ListNode> stack = new Stack<ListNode>();
    ListNode cur = head;
    int length = 0;
    while(cur != null){
        stack.push(cur);
        cur = cur.next;
        length++;
    }
    //System.out.printf("  "+length);
    cur = head;
    ListNode cur_unsort = head;
    for(int i = 0; i < length; i++){
        if(i%2 == 0){
            cur_unsort = cur.next;
            cur.next = stack.pop();
            cur = cur.next;
        }
        else{
            cur.next = cur_unsort;
            cur = cur.next;
            cur_unsort = cur_unsort.next;
        }

        //System.out.printf("  "+cur.val);
    }
    cur.next = null;

    return;
}

reverse node list: node n-1, node n-2, …….

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode reverseList(ListNode head) {
    //1
    if(head == null){
        return head;
    }
    //2
    ListNode cur = head.next;
    head.next = null;
    //3.......
    while(cur != null){
        ListNode store = cur.next;
        cur.next = head;
        head = cur;
        cur = store;
    }
    
    return head;
}




  1. 第一步还是先检查一下head有没有用，没用的话就直接出去，拿一个test case，白拿的分数。
  2. null <- 1（head） 2（cur） -> 3 -> 4 -> 5
  3. null <- 1（head） 2（cur） -> 3（store） -> 4 -> 5
    3.1 null <- 1（head） <- 2（cur） 3（store） -> 4 -> 5
    3.2 null <- 1 <- 2（head） 3（cur/store） -> 4 -> 5