`
betakoli
  • 浏览: 168452 次
社区版块
存档分类
最新评论

LeetCode Reorder List

 
阅读更多

Given a singly linked list LL0→L1→…→Ln-1→Ln,
reorder it to: L0→LnL1→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-leetcode题解之143-Reorder-List

    python python_leetcode题解之143_Reorder_List

    LeetCode最全代码

    * [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...

    Leetcode题目+解析+思路+答案.pdf

    - **Reorder List**:按照特定规则重新排列链表。 - **Partition List**:将链表按值分割成两个部分。 - **Add Two Numbers**:两个非负整数相加,结果存储在链表中。 - **Copy List with Random Pointer**:...

    leetcode中325题python-leetcode:leetcode

    leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 ...reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动

    python 教程 leetcode 代码模板-.Linked-List-Two-Pointers-List.md

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

    LeetCode:LeetCode解决方案

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

    python-leetcode面试题解之第143题重排链表-题解.zip

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

    java-leetcode题解之第143题重排链表.zip

    public ListNode reorderList(ListNode head) { if (head == null || head.next == null) return head; // 分离奇数和偶数链表 ListNode odd = head, even = head.next, evenHead = even; while (even != null...

    LeetCode练习答案

    - **重排链表(Reorder List)**: 给定一个单链表L,将其重新排列为A-B-A-B形式。 - **划分链表(Partition List)**: 将链表中所有小于x的节点移到所有大于或等于x的节点之前。 - **两数相加(Add Two Numbers)**: 给定...

    重排链表1

    在提供的 `Solution` 类中,`reorderList` 函数实现了以上步骤。首先检查链表是否为空,然后执行上述三个步骤。这个函数的时间复杂度是 O(n),因为我们需要遍历链表两次,一次找到中间节点,一次进行合并;空间...

    oj题.zip

    3. **143.py** - 可能对应的是LeetCode的143题,"Reorder List"(重排链表),涉及链表操作和双指针技巧。 4. **140.py** - 可能是LeetCode的140题,"Word Break II"(单词拆分II),这是一道动态规划问题,需要...

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    1. **Reorder List** (重新排序链表): 这个问题涉及到链表的操作,包括遍历链表、找到中间节点以及翻转链表的部分子集。在Java中,链表通常用`LinkedList`类来实现,解决问题的关键在于理解和操作链表节点的指针。 ...

Global site tag (gtag.js) - Google Analytics