数据结构与算法中链表的多样操作：合并、拆分及回文判定

2天前发布 gsjqwyl

4 0 0

数据结构与算法中链表的多元操作：合并、分割及回文判断

1. 链表的合并

题目

将两个升序排列的链表合并成一个新的升序链表并返回。新链表由给定的两个链表的所有节点拼接而成。

示例

输入：l1 = [1,2,4]，l2 = [1,3,4] 输出：[1,1,2,3,4,4]
输入：l1 = []，l2 = [] 输出：[]
输入：l1 = []，l2 = [0] 输出：[0]

分析

可以采用迭代的方法来解决这个问题。核心思路是不断比较两个链表当前节点的值，将较小的节点连接到新链表中。具体步骤如下：

首先处理两个链表都不为空的情况，通过循环比较两个链表当前节点的值，将较小的节点接入新链表：

while (list1 && list2) {
    if (list1->val < list2->val) {
        if (Tail == NULL) {
            Head = Tail = list1;
        } else {
            Tail->next = list1;
            Tail = list1;
        }
        list1 = list1->next;
    } else {
        if (Tail == NULL) {
            Head = Tail = list2;
        } else {
            Tail->next = list2;
            Tail = list2;
        }
        list2 = list2->next;
    }
}

然后处理其中一个链表为空的情况，直接将非空链表剩余部分接入新链表：

if (list1 == NULL) {
    return list2;
}
if (list2 == NULL) {
    return list1;
}
if (list1) {
    Tail->next = list1;
    Tail = list1;
}
if (list2) {
    Tail->next = list2;
    Tail = list2;
}
return Head;

2. 链表的分割

题目

给定链表的头指针 ListNode* pHead 和一个值 x，编写代码将所有小于 x 的节点排在其余节点之前，且不改变原数据的顺序，返回重新排列后的链表头指针。

示例

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

分析

可以通过创建两个新链表来分别存储小于 x 和大于等于 x 的节点，最后将两个链表连接起来。为了方便处理边界情况，使用哨兵位头节点：

首先创建两个哨兵位头节点分别用于存储小于 x 和大于等于 x 的节点：

ListNode* SmallHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* SmallTail = SmallHead;
ListNode* BigHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* BigTail = BigHead;
ListNode* cur = pHead;

遍历原链表，将节点根据值的大小分别接入对应的链表：

while (cur) {
    if (cur->val < x) {
        ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
        SmallTail->next = temp;
        SmallTail = temp;
        SmallTail->val = cur->val;
    } else {
        ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
        BigTail->next = temp;
        BigTail = temp;
        BigTail->val = cur->val;
    }
    cur = cur->next;
}

最后连接两个链表并返回结果：

BigTail->next = NULL;
SmallTail->next = BigHead->next;
return SmallHead->next;

3. 链表的回文结构判断

题目

给定链表的头指针 A，设计一个时间复杂度为 O(n)、额外空间复杂度为 O(1) 的算法判断其是否为回文结构。

示例

输入：1->2->2->1 输出：true

分析

可以通过找到链表的中间节点，将后半部分链表反转，然后比较前后两部分是否相同来判断是否为回文结构。

首先找到链表的中间节点：

ListNode* fast = A;
ListNode* slow = A;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}

然后反转后半部分链表：

ListNode* reverse_tail = slow;
ListNode* slow_prev = slow;
slow = slow->next;
ListNode* slow_next = slow->next;
while (slow) {
    slow->next = slow_prev;
    slow_prev = slow;
    slow = slow_next;
    slow_next = slow_next->next;
}

接着比较前后两部分是否相同：

// 处理特殊情况
if (slow == NULL || slow->next == NULL) {
    return false;
}
if (slow->next == NULL) {
    if (A->val == slow->val) {
        return true;
    } else {
        return false;
    }
}

// 正常情况比较
while (slow_prev != reverse_tail) {
    if (slow_prev->val == A->val) {
        A = A->next;
        slow_prev = slow_prev->next;
    } else {
        return false;
    }
}

// 处理奇偶不同情况
if (slow_prev != A) {
    if (slow_prev->val == A->val) {
        return true;
    } else {
        return false;
    }
}
return true;