本文共 2223 字,大约阅读时间需要 7 分钟。
给定一个链表 L0 -> L1 ->...->Ln,要求对链表进行重新排序,排序后为:L0->Ln->L1->Ln-1->... 例子:
第一个想到的肯定就是利用栈了。把每个节点依次添加到栈中,最后每次取首(start)尾(end)元素进行连接。具体看代码。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) return ; ArrayListlist = new ArrayList<>(); ListNode h = head; while (h != null) { list.add(h); h = h.next; } h = new ListNode(0); int start = 0, end = list.size() - 1; while (start <= end) { if (start == end) { h.next = list.get(start); h.next.next = null; break; } else { h.next = list.get(start); h.next.next = list.get(end); h.next.next.next = null; h = h.next.next; } start++; end--; } }}
效果并不是很理想,有待改进。
使用快慢指针找到链表的中点,继而只将链表的后半部分存入栈中。 代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) return ; ArrayListlist = new ArrayList<>(); // 只存储链表后半部分的节点 ListNode slow = head, fast = head, h = new ListNode(0); while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } boolean ou = false; // 判断节点个数的奇偶性 if (fast.next != null) ou = true; slow = slow.next; while (slow != null) { list.add(slow); slow = slow.next; } fast = head; int i = list.size() - 1; while (i >= 0) { h.next = fast; ListNode tmp = fast.next; fast.next = list.get(i--); h = fast.next; fast = tmp; } if (ou) h.next = null; else { h.next = fast; fast.next = null; } }}
转载地址:http://txesi.baihongyu.com/