leetCode解题报告之Reorder List-蒲公英云

leetCode解题报告之Reorder List

题目：

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}.

分析：

看到这个题目，我们首先容易想到的就是把链表分成两半，然后把后半部分链表进行逆序一下，之后再和前半部分结合起来就

可以将这道题目AC了！

两个要解决的问题：

1.如何快速的确定链表的中间位置的结点

2.如何将一个链表逆序，并且符合要求“You must do this in-place without altering the nodes’ values”

代码实现：

package cn.xym.leetcode;
class ListNode {
    public int val;
    public ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class ReorderList {
    public void reorderList(ListNode head) {
        /*先判断传入的链表是否为空*/
        if (head == null)
            return ;
        /*[快速求出链表的中间结点]通过两个结点，一个走1个步长，一个走2个步长，最后算出链表的中间结点middleNode*/
        ListNode middleNode = head;
        ListNode stepNode = head;
        while (stepNode != null && stepNode.next != null && stepNode.next.next != null){
            middleNode = middleNode.next;
            stepNode = stepNode.next.next;
        }
        /*将链表中间结点之后的链表（链表的后半部分）逆序*/
        ListNode T = middleNode.next;
        middleNode.next = null;
        if (T == null)
            return ;
        ListNode S = T.next;
        boolean flag = true;
        while (T != null && S != null){
            ListNode temp = S.next;
            S.next = T;
            if (flag) {
                T.next = null;
                flag = false;
            }
            T = S;
            S = temp;
        }
        /*完成链表前半部分和逆序后的后半部分的结合！*/
        while (T != null && head != null){
            ListNode temp1 = head.next;
            ListNode temp2 = T.next;
            head.next = T;
            T.next = temp1;
            head = temp1;
            T = temp2;
        }
    }
    public static void main(String[] args) {
        ReorderList list = new ReorderList();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = null;
        list.reorderList(node1);
        while (node1 != null){
            System.out.println(node1.val);
            node1 = node1.next;
        }
    }
}