AlgoPress | AlgoPress

0143-重排链表

https://leetcode.cn/problems/reorder-list

给定一个单链表 L 的头节点 head ，单链表 L 表示为： L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为： L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 10^4]
1 <= node.val <= 1000

思路

逐步遍历，拿取最后一个节点过来，插入到当前节点后面，去掉最后节点当 cur 节点 next == null 或者 next.next == null 停止循环

参考代码

csharp

public class Solution {
    public void ReorderList(ListNode head) {
    	while(head != null){
    		ListNode last = head;
    		ListNode pre = head;
    		
    		if(head.next == null || head.next.next == null){
    			return;
    		}

    		//找寻最后一个节点
    		while(last.next != null){
    			pre = last;
    			last = last.next;
    		}
    		pre.next = null;

    		ListNode next = head.next;
    		head.next = last;
    		last.next = next;

    		head = next;
    	}
    }
}

思路2【官方】

找寻链表中点，快慢指针
将后面链表的翻转
合并两个链表

csharp

class Solution {

	private ListNode FindMid(ListNode head){
		ListNode dummyHead = new ListNode();
		dummyHead.next = head;
		ListNode fast = dummyHead;
		ListNode slow = dummyHead;
		while(fast != null && fast.next != null ){
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}

	private ListNode FindLast(ListNode head){
		while(head.next != null){
			head = head.next;
		}
		return head;
	}

	private ListNode Reverse(ListNode head){
		ListNode pre = null;
		ListNode p = head;
		while(p != null){
			ListNode next = p.next;
			p.next = pre;
			pre = p;
			p = next;
		}
		head.next = null;
		return pre;
	}

	private ListNode MergeTwoLists(ListNode head1, ListNode head2){
		ListNode dummyHead = new ListNode();
		ListNode curNode = dummyHead;

		while(head1 != null && head2 != null){
			curNode.next = head1;
			curNode = curNode.next;
            head1 = head1.next;

			curNode.next = head2;
			curNode = curNode.next;
			head2 = head2.next;
		}
		if(head1 != null){
			curNode.next = head1;
		}
		if(head2 != null){
			curNode.next = head2;
		}

		return dummyHead.next;
	}


    public void ReorderList(ListNode head) {
    	if(head == null || head.next == null){
    		return;
    	}
    	ListNode mid = FindMid(head);
    	ListNode secHead = mid.next;
    	mid.next = null;
        
    	ListNode sec = Reverse(secHead);
    	head = MergeTwoLists(head,sec);
    }
}

0143-重排链表 #

思路 #

参考代码 #

思路2【官方】 #

0143-重排链表

思路

参考代码

思路2【官方】