day-23 重排链表

参考了答案。。。。。。

思路：利用快慢指针找到中间节点，再将后半部分利用头插法倒置，最后将两部分拼接起来

注意：分清ListNode t=null 未分配空间和ListNode t=new Lis他Node() 分配了空间

code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    public void reorderList(ListNode head) {

     ListNode mid=findmid(head);    //找到中间节点
     ListNode a=head;
     ListNode b=reverse(mid.next);//倒置后半部分
     mid.next=null;//将连链表划分为两部分
     merge(a,b);
    }

    public ListNode findmid(ListNode head){

        ListNode t=new ListNode();
        t.next=head;
        ListNode fast=t,slow=t;
        while(fast!=null&&fast.next!=null){

            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head){

      ListNode reverse=null;
      while(head!=null){

        ListNode next=head.next;
        head.next=reverse;
        reverse=head;
        head=next;
      }
      return reverse;
    }

    public ListNode merge(ListNode l1,ListNode l2){

        ListNode head=new ListNode();
        while(l1!=null&&l2!=null){

            head.next=l1;
            l1=l1.next;
            head=head.next;
            head.next=l2;
            l2=l2.next;
            head=head.next;
        }
        while(l1!=null){

            head.next=l1;
            l1=l1.next;
            head=head.next;
        }
        while(l2!=null){

            head.next=l2;
            l2=l2.next;
            head=head.next;
        }
        return head.next;
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/136808182

目录