重排链表

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：进制转换