题解 | #重排链表#
重排链表
https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b
普通做法:用一个数组集合保存下来,然后按需遍历。
public class Solution { public void reorderList(ListNode head) { if(head==null) return; // 初级:使用集合存储然后按需遍历 List<ListNode> res = new ArrayList<>(); ListNode node = head; while(node!=null){ res.add(node); node = node.next; } // 按需遍历,在原链表上修改 int i = 0,j = res.size()-1; while(i<j){ res.get(i).next = res.get(j); i++; if(i==j) break; res.get(j).next = res.get(i); j--; } res.get(i).next = null; } }
进阶:不适用外部空间,找到中间节点截断;然后将后半部分翻转;最后两部分直接映射
public class Solution { public void reorderList(ListNode head) { if(head==null || head.next==null) return; // 找到中间节点 ListNode mid = middle(head); // 后半部分节点位置 ListNode l2 = reverse(mid.next); ListNode l1 = head; // 截取了 mid.next = null; mapping(l1,l2); } // 考点:如何找到一个链表的中间节点?双指针 public ListNode middle(ListNode head){ ListNode slow = head,fast=head; while(fast.next!=null && fast.next.next!=null){ slow = slow.next; fast = fast.next.next; } return slow; } // 考点:翻转链表,这里用递归的形式 public ListNode reverse(ListNode node){ if(node.next == null || node==null) return node; ListNode pre = reverse(node.next); node.next.next = node; node.next = null; return pre; } public void mapping(ListNode l1,ListNode l2){ // 保留后一个节点 ListNode l1Temp=null,l2Temp=null; while(l1!=null && l2!=null){ l1Temp = l1.next; l2Temp = l2.next; l1.next = l2; l1 = l1Temp; l2.next = l1; l2 = l2Temp; } } }