【LeetCode】Reorder List

2309 단어 LeetCodelistmerge
다음으로 전송:http://www.programcreek.com/2013/12/in-place-reorder-a-singly-linked-list-in-java/
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example, Given {1,2,3,4} , reorder it to {1,4,2,3} .
brute force 시간 초과,사고방식:
  • Break list in the middle to two lists (use fast & slow pointers)
  • Reverse the order of the second list
  • Merge two list back together
  • /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public void reorderList(ListNode head) {
             if (head == null || head.next == null || head.next.next == null) {
    			return ;
    		}
    		ListNode fast = head;
        	ListNode slow = head;
        	while (fast != null && fast.next != null) {
    			fast = fast.next.next;
    			slow = slow.next;
    			
    		}
        	ListNode head2 = null;
        	if (fast == null) {
    			head2 = slow;
    		}
        	else if (fast.next == null) {
    			head2 = slow.next;
    		}
        	slow = head;
        	while(slow.next != head2)
        		slow = slow.next;
        	slow.next = null;
        	
            head2 = reverse(head2);
            
            merge(head, head2);
        
        }
        public ListNode reverse(ListNode head)
        {
        	if (head == null || head.next == null) {
    			return head;
    		}
        	ListNode curListNode  = head.next;
        	ListNode preListNode = head;
        	while (curListNode.next != null) {
        		ListNode tmp = curListNode.next;
    			curListNode.next = preListNode;
    			preListNode = curListNode;
    			curListNode = tmp;
    		}
        	curListNode.next = preListNode;
        	head.next = null;
        	head = curListNode;
        	return head;
        }
        public void merge(ListNode head1, ListNode head2)
        {
        	ListNode p1 = head1;
        	ListNode p2 = head2;
        	while (p1.next != null && p2.next != null) {
    			ListNode p1_next = p1.next;
    			ListNode p2_next = p2.next;
    			p1.next = p2;
    			p2.next = p1_next;
    			p1 = p1_next;
    			p2 = p2_next;
    			
    		}
            ListNode p1_next = p1.next;
        	p1.next = p2;
        	if (p1_next != null) {
    			p2.next = p1_next;
    		}
        	
        }
    }

    좋은 웹페이지 즐겨찾기