首页 > 代码库 > [leetcode]Reorder List

[leetcode]Reorder List

2024-07-13 06:27:10   222人阅读

Reorder List

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}.

算法思路：

设置快慢指针将前半段与后半段分开，然后将后半段逆序，再逐个插入前半段，时间复杂度O(n)，空间复杂度不定

思路1：

后半段的逆序，设置三指针，在原list基础上逆序，空间复杂度O(1)

后面还有一些题会用这个思路，这里就不实现了。

 

思路2：

后半段的逆序，借助栈，空间复杂度O(n)，代码简单

代码如下：

 1 public class Solution { 2     public void reorderList(ListNode head) { 3         if(head == null || head.next == null) return ; 4         ListNode hhead = new ListNode(0); 5         hhead.next = head; 6         ListNode fast = hhead; 7         ListNode slow = hhead; 8         while(fast != null && fast.next != null){ 9             fast = fast.next.next;10             slow = slow.next;11         }12         ListNode stackPart = slow.next;13         slow.next = null;14         Stack<ListNode> stack = new Stack<ListNode>();15         while(stackPart != null){16             stack.push(stackPart);17             stackPart = stackPart.next;18         }19         ListNode insert = head;20         while(!stack.isEmpty()){21             ListNode tem = stack.pop();22             tem.next = insert.next;23             insert.next = tem;24             insert = tem.next;25         }26     }27 }

 


联系
我们