143 Reorder List

重新排列一个List

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        if head is None:
            return None
        slow, fast = head, head 
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        # slow => middle node
        # 2nd. change the last part = > reverse linkedlist
        pre = slow
        cur = pre.next
        pre.next = None
        prev = None
        while cur:
            nxt = cur.next 
            cur.next = prev
            prev = cur
            cur = nxt
        # 3rd: connect list =[10,60,20,50,30] prev = [40]
        p = head
        while p and prev:
            t = p.next 
            p.next = prev 
            prev_nex = prev.next
            prev.next = t
            prev = prev_nex
            p = t
        return head

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null){
            return;
        }
        ListNode fast = head, slow = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode curr = slow.next;
        slow.next = null;
        ListNode prev = null;
        while(curr != null){
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        ListNode p = head;
        while(p != null && prev != null){
            ListNode t = p.next;
            p.next = prev;
            ListNode prev_nex = prev.next;
            prev.next = t;
            prev = prev_nex;
            p = t;
        }
        return;   
    }
}