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}
.
题目的思路是,找到中间节点,将后半截链表反转。将前半截链表和翻转后的链表进行遍历交叉组合。
/** * Definition for singly-linked list. * 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 ; ListNode p,q,pre; p = getMid(head); q = p.next; p.next=null; q=reverse(q); p=head; while(p!=null&&q!=null) { ListNode temp1 = p.next; ListNode temp2 = q.next; p.next=q; q.next=temp1; p=temp1; q=temp2; } } public static ListNode getMid(ListNode head) { ListNode p = head; ListNode q = head; while(q.next!=null&&q.next.next!=null) { q=q.next.next; p=p.next; } return p; } public static ListNode reverse(ListNode head) { ListNode q = null,pre; pre=head; if(pre.next!=null) { q=pre.next; pre.next=null; } while(q!=null) { ListNode temp=q.next; q.next=pre; pre=q; q=temp; } return pre; } }
相关推荐
python python_leetcode题解之143_Reorder_List
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
- **Reorder List**:按照特定规则重新排列链表。 - **Partition List**:将链表按值分割成两个部分。 - **Add Two Numbers**:两个非负整数相加,结果存储在链表中。 - **Copy List with Random Pointer**:...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 ...reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
def reorderList(self, head: ListNode) -> None: if not head or not head.next: return # 找到链表中点 mid = self.findMid(head) # 反转后半部分链表 l2 = mid.next mid.next = None l2 = self....
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
def reorderList(head): if not head or not head.next: return head mid = find_mid(head) next_to_mid = mid.next mid.next = None right = reverse_list(next_to_mid) left = head right_tail = None ...
public ListNode reorderList(ListNode head) { if (head == null || head.next == null) return head; // 分离奇数和偶数链表 ListNode odd = head, even = head.next, evenHead = even; while (even != null...
- **重排链表(Reorder List)**: 给定一个单链表L,将其重新排列为A-B-A-B形式。 - **划分链表(Partition List)**: 将链表中所有小于x的节点移到所有大于或等于x的节点之前。 - **两数相加(Add Two Numbers)**: 给定...
在提供的 `Solution` 类中,`reorderList` 函数实现了以上步骤。首先检查链表是否为空,然后执行上述三个步骤。这个函数的时间复杂度是 O(n),因为我们需要遍历链表两次,一次找到中间节点,一次进行合并;空间...
3. **143.py** - 可能对应的是LeetCode的143题,"Reorder List"(重排链表),涉及链表操作和双指针技巧。 4. **140.py** - 可能是LeetCode的140题,"Word Break II"(单词拆分II),这是一道动态规划问题,需要...
1. **Reorder List** (重新排序链表): 这个问题涉及到链表的操作,包括遍历链表、找到中间节点以及翻转链表的部分子集。在Java中,链表通常用`LinkedList`类来实现,解决问题的关键在于理解和操作链表节点的指针。 ...