leetcode143~Reorder List

本文主要是介绍leetcode143~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}

思路： 1 利用俩指针找到中间节点，将链表分为两个部分
2 对后半部分的链表进行逆序
3 合并两个链表

public void reorderList(ListNode head) {if(head==null || head.next==null) return;ListNode fast = head;ListNode slow = head;while(fast.next!=null && fast.next.next!=null) {slow = slow.next;fast = fast.next.next;}//此时slow是中间的节点ListNode rhead = slow.next;slow.next = null;rhead = reverse(rhead);//合并链表while(head!=null && rhead!=null) {ListNode tmp1 = head.next;ListNode tmp2 = rhead.next;head.next = rhead;rhead.next = tmp1;head = tmp1;rhead = tmp2;}}//翻转private ListNode reverse(ListNode head) {ListNode pre = null;while(head!=null) {ListNode tmp = head.next;head.next = pre;pre = head;head = tmp;}return pre;}

这篇关于leetcode143~Reorder List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---