leetcode经典编程题（8）

2019-11-06 08:36:36

字体：大中小

来源：转载

供稿：网友

第（8）题 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}. 题意就是将原序列中的后（n/2）项反转，再隔项差入到前（n/2）项的序列中。思路：最直接的想法就是分别获取前，后（n/2）项，再将和一半反转，插入到前一半中。如何反转？其实就是一个不断向链表头部添加结点的过程。代码如下：

/** * 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){ return; } int len = 0; ListNode next = head; while(next != null){ next = next.next; len++; } if(len == 1 || len == 2 ){ return; } int n = len%2 == 0 ? len/2 : len/2+1 ; next = head; for(int i = 1; i < n; i++){ next = next.next; } ListNode temp = next.next; next.next = null; next = head; ListNode newHead = ref(temp); while(newHead != null){ ListNode n1 = next.next; ListNode n2 = newHead.next; next.next = newHead; newHead.next = n1; next = n1; newHead = n2; } } public ListNode ref(ListNode head){ if(head == null || head.next == null){ return head; } ListNode next = head.next; head.next = null; while(next != null){ ListNode temp = next.next; next.next = head; head = next; next = temp; } return head; }}

上一篇：关于 Juniper Networks 引发的route命令的学习

下一篇：漫步数学分析二十四——连续函数空间