99.Reorder List-重排链表（中等题）

本文主要是介绍99.Reorder List-重排链表（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

重排链表

题目

给定一个单链表L: L0→L1→…→Ln-1→Ln,
重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。
样例

给出链表 1->2->3->4->null，重新排列后为1->4->2->3->null。
题解

1.辅助栈

先遍历一遍链表，将节点依次入栈，再将指针移到到头结点结合依次弹栈操作就可以获取L0→Ln，L1→Ln-1这样的节点序列。节点数为偶数的链表结束标志为指针与栈顶元素相遇，即h.next != stack.peek()，节点数为奇数的链表结束标志为指针与栈顶节点相同，即h != stack.peek()。注意遍历结束时将最后一个栈顶元素的后继节点置为Null。

/*** Definition for ListNode.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int val) {*         this.val = val;*         this.next = null;*     }* }*/ 
public class Solution {/*** @param head: The head of linked list.* @return: void*/public void reorderList(ListNode head) {  if (head == null || head.next == null || head.next.next == null){return;}Stack<ListNode> stack = new Stack<ListNode>();ListNode h = head;while (h != null){stack.push(h);h = h.next;}h = head;while (h.next != stack.peek() && h != stack.peek()){ListNode tail = stack.pop();ListNode tmp = h.next;h.next = tail;tail.next = tmp;h = tmp;}stack.peek().next = null;}
}

2.先找到链表的中点，将中点后的链表翻转，再依次插入到前半条链表各个节点后。如1->2->3->4->5->6，找到中点3，再翻转链表得到1->2->3->6->5->4，再将6->5->4依次插入到1->2->3的后面得到1->6->2->5->3->4。

public class Solution
{private ListNode reverse(ListNode head){ListNode newHead = null;while (head != null){ListNode temp = head.next;head.next = newHead;newHead = head;head = temp;}return newHead;}private void merge(ListNode head1, ListNode head2){int index = 0;ListNode dummy = new ListNode(0);while (head1 != null && head2 != null){if (index % 2 == 0){dummy.next = head1;head1 = head1.next;}else{dummy.next = head2;head2 = head2.next;}dummy = dummy.next;index++;}if (head1 != null){dummy.next = head1;}else{dummy.next = head2;}}private ListNode findMiddle(ListNode head){ListNode slow = head, fast = head.next;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}public void reorderList(ListNode head){if (head == null || head.next == null){return;}ListNode mid = findMiddle(head);ListNode tail = reverse(mid.next);mid.next = null;merge(head, tail);}
}