143.重排链表

发表于 | 分类于
字数统计: 380 | 阅读时长 ≈ 1

一、题目描述

给定一个单链表 L：L0→L1→…→L**n-1→Ln ，
将其重新排列后变为： L0→L**n→L1→L**n-1→L2→L**n-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

1
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

1
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

二、题解

1.算法描述

  1. 双指针+翻转链表
  2. 使用栈

2.个人分析

我使用的是法一：

  1. 使用快慢双指针找到链表中点
  2. 将后半段链表翻转
  3. 拼接两个链表

简述一下法二：

  1. 先将所有节点进栈
  2. 边遍历，边出栈（出后半段就够了）

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

void reorderList(struct ListNode *head)
{
    if (!head || !head->next || !head->next->next)
        return;
    //找到中点
    struct ListNode *fast = head, *slow = head, *right;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    right = slow->next;
    slow->next = NULL;
    //翻转后半部分
    struct ListNode *p = right, *q, *r;
    r = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        q->next = r;
        r = q;
    }
    right = q;
    //遍历并连接
    struct ListNode *l1 = head, *l2 = right, *l1next = head->next, *l2next = right->next;
    while (l2)
    {
        l2->next = l1next;
        l1->next = l2;
        l1 = l1next;
        l1next = l1next->next;
        l2 = l2next;
        if (l2next)
            l2next = l2next->next;
        else
            break;
    }
}

真是有史以来写的又臭又长的代码！