leetcode143 重排链表

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路：分成两个链表，第二个逆置，然后插入即可。

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * public class ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * ListNode next;
     
    
   

    

     

    
    

     

       * ListNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public void reorderList(ListNode head) {
     
    
   

    

     

    
    

     
 if (head == null || head.next == null || head.next.next == null) {
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 //找中点，链表分成两个
     
    
   

    

     

    
    

     

       ListNode slow = head;
     
    
   

    

     

    
    

     

       ListNode fast = head;
     
    
   

    

     

    
    

     
 while (fast.next != null && fast.next.next != null) {
     
    
   

    

     

    
    

     

       slow = slow.next;
     
    
   

    

     

    
    

     

       fast = fast.next.next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       ListNode newHead = slow.next;
     
    
   

    

     

    
    

     

       slow.next = null;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //第二个链表倒置
     
    
   

    

     

    
    

     

       newHead = reverseList(newHead);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //链表节点依次连接
     
    
   

    

     

    
    

     
 while (newHead != null) {
     
    
   

    

     

    
    

     

       ListNode temp = newHead.next;
     
    
   

    

     

    
    

     

       newHead.next = head.next;
     
    
   

    

     

    
    

     

       head.next = newHead;
     
    
   

    

     

    
    

     

       head = newHead.next;
     
    
   

    

     

    
    

     

       newHead = temp;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      private ListNode reverseList(ListNode head) {
     
    
   

    

     

    
    

     
 if (head == null) {
     
    
   

    

     

    
    

     
 return null;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       ListNode tail = head;
     
    
   

    

     

    
    

     

       head = head.next;
     
    
   

    

     

    
    

     

       tail.next = null;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while (head != null) {
     
    
   

    

     

    
    

     

       ListNode temp = head.next;
     
    
   

    

     

    
    

     

       head.next = tail;
     
    
   

    

     

    
    

     

       tail = head;
     
    
   

    

     

    
    

     

       head = temp;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return tail;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103405381