链表的重排序

青旅半醒 2022-05-23 04:40 120阅读 0赞

![这里写图片描述][70]

import java.util.*;
    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)
                return;
            //(1)快慢指针找到中间节点
            ListNode slow=head;
            ListNode fast=head;
            while(fast.next!=null&&fast.next.next!=null)
            {
                 fast=fast.next.next;
                 slow=slow.next;
            }
    
            //(2)拆分链表,并且反转后面一部分链表
            ListNode after=slow.next;
            slow.next=null;
            //ListNode pre=reverseList(after);
            ListNode pre=null;
            while(after!=null){
    
                 ListNode tmp=after.next;
                 after.next=pre;
                 pre=after;
                 after=tmp;
            }
    
            //(3)合并两个链表
            ListNode first=head;
            after=pre;
            while(first!=null&&after!=null){
                ListNode ftemp=first.next;
                ListNode atemp=after.next;
                first.next=after;
                first=ftemp;
                after.next=first;
                after=atemp;
            }
    
        }
    
        //遍历链表
        public void printList(ListNode head)
        {
             while(head!=null)
             {
                 System.out.print(head.val+" ");
                 head=head.next;
             }
             System.out.println();
        }
        public static void main(String[]args){
            // System.out.println("Hello World!");
             ListNode head=new ListNode(1);
             head.next=new ListNode(3);
             head.next.next=new ListNode(2);
             Solution s=new Solution();
             s.reorderList(head);
             s.printList(head);
    
        }
    
    }

![这里写图片描述][70 1]

[70]: /images/20220523/861b8ceb3a1f4ff88fa924ddf535dfcb.png
[70 1]: /images/20220523/f4693cbfee2a4adeba7703d0604ae54b.png