LinkedList

Question 1

Reorder List

Given a singly linked list L: 1->2->3->4->5->6
reorder it to 1->6->2->5->3->4;

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Answer 1

public void reorderList(ListNode head) {
        HashMap map = new HashMap<>();
        for(int i = 1;head != null;head = head.next,i++){
            map.put(i,head);
        }
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for(int i = 1,j = map.size();i <= j;i++,j--){   //1,2,3,4
            curr.next = map.get(i);                     //curr->1
            if(i!= j) map.get(i).next = map.get(j);     //1->4
            map.get(j).next = null;                     //4->null
            curr = map.get(j);                          ///curr = 4,then 1->4
        }
    }