linkedlist and array

存取效率

Array > LinkedList

LinkedList要从头开始移动指针而Array是randomaccess

插入元素：LinkedList更灵活

LinkedList练习

Reverse LinkedList

翻转LinkedList

1->2->3->4->null

4->3->2->1->null

//0->1->2->3->4
//0<-1 2->3->4
//0<-1<-2 3->4->5
//0<-1<-2<-3 4->5
//0<-1<-2<-3<-4 5
//0<-1<-2<-3<-4<-5
public ListNode reverse(ListNode head){
    // write your code here
        if(head == null)return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //0<->1->2->3->4->5
        //0<->1 2->3->4->5
        //0<->1<-2 3->4->5
        ListNode cur = head;
        ListNode pre = dummy;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //0<->1<-2<-3<-4<-5
        //head = 1,
        //prev = 5,cur = null
        head.next = null;
        return pre;
}

Reverse Linked ListII

Reverse a linked list from position m to n.

Notice

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Challenge

Reverse it in-place and in one-pass

public ListNode reverseBetween(ListNode head, int m, int n) {
        // 0->1->2->3->4->5->6
        // m=2,n =4
        // prev = 1,cur = 2
        //   0->1<- 2  3->4->5->6 start = 2, start_prev = 1
        // 2:0->1<->2<-3 4->5->6
        // 3:0->1<->2<-3<-4 5->6
        // 4:0->1<->2<-3<-4<-5 6 prev = 5, cur = 6, s_prev.next -> prev, start -> cur
        // 5:0->1-> 5->4->3->2->6
        // write your code here
        if(head ==  null || head.next == null)return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode start_prev = dummy;
        //find start_prev. e.g:m = 1, start_prev = 0,start = 1
        for(int i = 1; i < m; i++){
            start_prev = start_prev.next;
        }
        ListNode start = start_prev.next;
        ListNode cur = start;
        ListNode prev = start_prev;
        //start reverse n = 3.n-m = 2
        for(int i = m; i <= n; i++){
            // 2:0->1->2<-3 4->5->6
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        // 4:0->1<->2<-3<-4<-5 6 prev = 5, cur = 6, s_prev.next -> prev, start -> cur
        // 5:0->1-> 5->4->3->2->6
        start_prev.next = prev;
        start.next = cur;
        return dummy.next;
    }

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.

Example
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

public ListNode reverseKGroup(ListNode head, int k) {
        // write your code here
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        // 0-> 1->2->3->4->5 
        // 0 
        while(prev != null){
            prev = reverseKNode(prev,k);
        }
        return dummy.next;
    }
    // 0->1->2->3->4->5 prev = 0, cur = 1
    // 0<->1 2->3->4->5 start for
    // 0<->1<-2 3->4->5 end for prev = 2, cur = 3
    // 0->2->1->3->4->5 
    public ListNode reverseKNode(ListNode head, int k){
        ListNode last = head.next;
        ListNode prev = head;
        ListNode cur = head.next;
        ListNode temp = null;
        ListNode nk = head;
        //0->1->2 nk to 2
        for(int i = 0;i < k; i++){
            nk = nk.next;
            if(nk == null){
                return null;
            }
        }
        //0<->1<-2 3->4->5 cur = 3, prev = 2
        for(int i = 0; i < k; i++){
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        // 0->2->1->3->4->5  1=last, head.next->prev, 
        head.next = nk;//nk == prev
        last.next = cur;
        return last;
    }