Given a singly linked list L: L 0→L 1→…→L n-1→L n, reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…

Bertha 。 2022-05-26 04:25 168阅读 0赞

> 题目描述

Given a singly linked list L: L 0→L 1→…→L n-1→L n,  
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-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\}.

> 思路：  
> 快慢指针找到中间结点，然后根据中间结点，将链表断开，翻转后面部分链表，然后将两个链表合并

/** * 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 slow = head;
            ListNode fast = head;
            //快慢指针找到中间结点
            while(fast != null && fast.next != null && fast.next.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            //断开链表，fast指向后半部分链表，head仍然是头结点，之前前半部分链表
            fast = slow;
            slow = slow.next;
            fast.next = null;
            //翻转链表
            ListNode lastHead = ReverseNode(slow);
            ListNode newHead = head;
            head = head.next;
            //合并链表
            while(head != null && lastHead != null){
                newHead.next = lastHead;
                lastHead = lastHead.next;
                newHead = newHead.next;
                newHead.next = head;
                head = head.next;
                newHead = newHead.next;
            }
            if(head != null)
                newHead.next = head;
            if(lastHead != null)
                newHead.next = lastHead;
        }
        private ListNode ReverseNode(ListNode head){
            ListNode prev = null;
            ListNode curr = head;
            while(curr != null && curr.next != null){
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            curr.next = prev;
            return curr;
        }
    }