[数据结构与算法]【LeetCode每日一题】——143.重排链表

一【题目类别】

• 双指针

二【题目难度】

• 中等

三【题目编号】

• 143.重排链表

四【题目描述】

• 给定一个单链表 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$

八【时间频度】

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package DoublePointer;

public class p143_ReorderList {

    int val;
    p143_ReorderList next;

    p143_ReorderList() {
    }

    p143_ReorderList(int val) {
        this.val = val;
    }

    p143_ReorderList(int val, p143_ReorderList next) {
        this.val = val;
        this.next = next;
    }

    public static void main(String[] args) {
        p143_ReorderList l1 = new p143_ReorderList(1);
        p143_ReorderList l2 = new p143_ReorderList(2);
        p143_ReorderList l3 = new p143_ReorderList(3);
        p143_ReorderList l4 = new p143_ReorderList(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = null;
        reorderList(l1);
        p143_ReorderList cur = l1;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public static void reorderList(p143_ReorderList head) {
        p143_ReorderList slow = head;
        p143_ReorderList fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        p143_ReorderList l1 = head;
        p143_ReorderList l2 = slow.next;
        slow.next = null;
        l2 = reverse(l2);
        merge(l1, l2);
    }

    public static p143_ReorderList reverse(p143_ReorderList head) {
        p143_ReorderList pre = null;
        p143_ReorderList cur = head;
        while (cur != null) {
            p143_ReorderList temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static void merge(p143_ReorderList l1, p143_ReorderList l2) {
        p143_ReorderList temp1;
        p143_ReorderList temp2;
        while (l1 != null && l2 != null) {
            temp1 = l1.next;
            temp2 = l2.next;
            l1.next = l2;
            l1 = temp1;
            l2.next = l1;
            l2 = temp2;
        }
    }

}

2. C语言版

#include<stdio.h>
#include<stdlib.h>
#include<stdlib.h>

struct ListNode {
	int val;
	struct ListNode *next;
};

struct ListNode* reverse_p143_ReorderList(struct ListNode* head)
{
	struct ListNode* dummyHead = NULL;
	struct ListNode* cur = head;
	while (cur != NULL)
	{
		struct ListNode* temp = cur->next;
		cur->next = dummyHead;
		dummyHead = cur;
		cur = temp;
	}
	return dummyHead;
}

void merge(struct ListNode* h1, struct ListNode* h2)
{
	struct ListNode* temp1;
	struct ListNode* temp2;
	while (h1 != NULL && h2 != NULL)
	{
		temp1 = h1->next;
		temp2 = h2->next;
		h1->next = h2;
		h1 = temp1;
		h2->next = h1;
		h2 = temp2;
	}
}

void reorderList(struct ListNode* head)
{
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast->next != NULL && fast->next->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	struct ListNode* l1 = head;
	struct ListNode* l2 = slow->next;
	slow->next = NULL;
	l2 = reverse_p143_ReorderList(l2);
	merge(l1, l2);
}

/*主函数省略*/

十【提交结果】

1. Java语言版
   

2. C语言版