重排鏈表

2019-11-08 02:18:17

字體：大中小

來源：轉載

供稿：網友

給定一個單鏈表L: L0→L1→…→Ln-1→Ln, 重新排列后為：L0→Ln→L1→Ln-1→L2→Ln-2→… 必須在不改變節點值的情況下進行原地操作。

解決的方法很簡單,用快慢針或者計數的辦法找出中點,然后將鏈表分成前后兩塊,后面的按規律插入前面的就行了這里記錄一下單鏈表逆序的方法我們用迭代的方法來逆序一個單鏈表,要經過如圖片描述的迭代偽代碼描述

head->next = PRev;prev = head;head = next;next = head->next;

第一次迭代

/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param head: The head of linked list. * @return: void */ public void reorderList(ListNode head) { // write your code here if(head == null || head.next == null) return; //快慢針,找中間結點 ListNode p = head; ListNode q = head.next; while(q != null && q.next != null){ p = p.next; q = q.next.next; } //中間節點 q = p.next; p.next = null; //將后半段逆序 ListNode rHead = null; while(q != null) { ListNode r = q.next; q.next = rHead; rHead = q; q = r; } //向前半段插入 q = rHead; p = head; while(p != null && q != null) { ListNode rr = q.next; ListNode lr = p.next; q.next = lr; p.next = q; q = rr; p = lr; } }}

上一篇：藍橋杯算法提高打水問題邏輯策略貪心

下一篇：華為OJ：進制轉換