首页 > 代码库 > 【leetcode】Reorder List

【leetcode】Reorder List

2024-07-12 08:38:59   219人阅读

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->4，从中间折断得到两个链表1->2和3->4，后面一个链表反转得到4->3，然后和第一个链表交错归并得到1->3->2->4;

再例如1->2->3->4->5，从中间折断得到两个链表1->2->3和4->5，后一个链表反转得到5->4，和第一个链表交错归并得到1->4->2->5->3;

代码如下：

 1 /** 2  * Definition for singly-linked list. 3  * class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13      private ListNode reverse(ListNode head){14          ListNode newHead = null;15          while(head != null){16              ListNode temp = head.next;17              head.next = newHead;18              newHead = head;19              head = temp;20          }21          return newHead;22      }23      24      private void newMerge(ListNode head1,ListNode head2){25          ListNode newHead = new ListNode(0);26          27          while(head1 != null && head2 != null){28              newHead.next = head1;29              head1 = head1.next;30              newHead = newHead.next;31              newHead.next = head2;32              head2 = head2.next;33              newHead = newHead.next;34          }35          if(head1 != null)36              newHead.next = head1;37          if(head2 != null)38              newHead.next = head2;39      }40      private ListNode findMiddle(ListNode head){41           ListNode slow = head;42           ListNode fast = head.next;43           while(fast != null && fast.next != null)44           {45               slow = slow.next;46               fast = fast.next.next;47           }48           return slow;49       }50     public void reorderList(ListNode head) {51         if(head == null || head.next == null)52             return;53         54         ListNode mid = findMiddle(head);55         ListNode tail = reverse(mid.next);56         mid.next = null;57         58         newMerge(head, tail);59     }60 }


联系
我们