数据结构编程题 链表

链表定义

以下为本文解题代码的链表定义。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int val = 0, ListNode* next = nullptr) : val(val), next(next) {}
};

递归删除结点

题目描述

设计一个递归算法，删除不带头结点的单链表 L 中的所有值为 x 的结点，并返回新的链表头节点。

解题代码

ListNode* deleteNodeRecur(ListNode* head, int x) {
    if (head == nullptr) return head;
    head->next = deleteNodeRecur(head->next, x);
    if (head->val == x) {
        ListNode* nextNode = head->next;
        delete head;
        return nextNode;
    }
    else {
        return head;
    }
}

删除结点

题目描述

在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法以实现上述功能。

解题代码

void deleteNode(ListNode* head, int x) {
    if (head->next == nullptr) return;
    while (head->next != nullptr) {
        if (head->next->val == x) {
            ListNode* p = head->next;
            head->next = head->next->next;
            delete p;
        }
        else {
            head = head->next;
        }
    }
}

反向输出结点值

题目描述

设 L 为不带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

解题代码

void reversePrint(ListNode* head) {
    if (head == nullptr) return;
    reversePrint(head->next);
    cout << head->val << " ";
}

删除最小值结点

题目描述

试编写在带头结点的单链表 L 中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。

解题代码

void deleteMinNode(ListNode* head) {
    if (head->next == nullptr) return;
    ListNode* preMinNode = head;
    ListNode* minNode = head->next;
    while (head->next != nullptr) {
        if (head->next->val < minNode->val) {
            preMinNode = head;
            minNode = head->next;
        }
        head = head->next;
    }
    preMinNode->next = preMinNode->next->next;
    delete minNode;
}

逆置链表

题目描述

试编写算法将带头结点的单链表就地逆置。所谓“就地”是指辅助空间复杂度为 O(1).

解题代码

void reverseList(ListNode* head) {
    ListNode* preNode = nullptr;
    ListNode* curNode = head->next;
    while (curNode != nullptr) {
        ListNode* tempNode = curNode->next;
        curNode->next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    head->next = preNode;
}

链表排序

题目描述

有一个带头结点的单链表 L，设计一个算法使其元素单调递增有序。

解题代码

选择排序

void selectSortList(ListNode* head) {
    ListNode* beginNode = head->next;
    while (beginNode != nullptr) {
        ListNode* curNode = beginNode;
        ListNode* minNode = curNode;
        int minVal = curNode->val;
        while (curNode != nullptr) {
            if (minVal > curNode->val) {
                minVal = curNode->val;
                minNode = curNode;
            }
            curNode = curNode->next;
        }
        swap(beginNode->val, minNode->val);
        beginNode = beginNode->next;
    }
}

插入排序

void insertSort(ListNode* head) {
    if (head->next == nullptr) return;
    ListNode* lastSorted = head; // 最后一个已排序结点
    ListNode* curNode = head->next; // 当前待排序结点
    while (curNode != nullptr) {
        if (lastSorted->val <= curNode->val) {
            lastSorted = lastSorted->next;
        }
        else {
            ListNode* preNode = head;
            while (preNode->next->val <= curNode->val) {
                preNode = preNode->next;
            }
            lastSorted->next = curNode->next;
            curNode->next = preNode->next;
            preNode->next = curNode;
        }
        curNode = lastSorted->next;
    }
}

寻找两链表的公共结点

题目描述

给定两个单链表，编写算法找出两个链表的公共结点。

解题代码

ListNode* publicNode(ListNode* head1, ListNode* head2) {
    ListNode* curNode1 = head1->next;
    ListNode* curNode2 = head2->next;
    while (curNode1 != curNode2) {
        if (curNode1 == nullptr) {
            curNode1 = head2->next;
        }
        else {
            curNode1 = curNode1->next;
        }
        if (curNode2 == nullptr) {
            curNode2 = head1->next;
        }
        else {
            curNode2 = curNode2->next;
        }
    }
    return curNode1;
}

分解单链表

题目描述

将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中含有原表中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

解题代码

ListNode* decomposeList(ListNode* head) {
    ListNode* bHead = new ListNode(-1);
    ListNode* bCurNode = bHead;
    if (head->next != nullptr) {
        head = head->next;
    }
    while (head != nullptr && head->next != nullptr) {
        bCurNode->next = new ListNode(head->next->val, nullptr);
        bCurNode = bCurNode->next;
        ListNode* tempNode = head->next;
        head->next = head->next->next;
        delete tempNode;
        head = head->next;
    }
    return bHead;
}

链表元素去重

题目描述

在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为不带头结点的单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素，例如（7, 10, 10, 21, 30, 42, 42, 42, 51, 70）将变为（7, 10, 21, 30, 42, 51, 70）。

解题代码

void deduplicateList(ListNode* head) {
    while (head != nullptr && head->next != nullptr) {
        if (head->val == head->next->val) {
            ListNode* tempNode = head->next;
            head->next = head->next->next;
            delete tempNode;
        }
        else {
            head = head->next;
        }
    }
}

合并有序单链表

题目描述

假设有两个按元素递增次序排列的线性表，均已带头结点的单链表形式存储。请编写算法将这两个单链表归并为一个按元素递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

解题代码

ListNode* mergeSortedList(ListNode* head1, ListNode* head2) {
    head1 = head1->next;
    head2 = head2->next;
    ListNode* head3 = new ListNode(-1);
    while (head1 != nullptr && head2 != nullptr) {
        if (head1->val <= head2->val) {
            // 头插法使得插入后逆序
            ListNode* newNode = head1;
            head1 = head1->next;
            newNode->next = head3->next;
            head3->next = newNode;
        }
        else {
            ListNode* newNode = head2;
            head2 = head2->next;
            newNode->next = head3->next;
            head3->next = newNode;
        }
    }
    while (head1 != nullptr) {
        ListNode* newNode = head1;
        head1 = head1->next;
        newNode->next = head3->next;
        head3->next = newNode;
    }
    while (head2 != nullptr) {
        ListNode* newNode = head2;
        head2 = head2->next;
        newNode->next = head3->next;
        head3->next = newNode;
    }
    return head3;
}

根据公共元素建立链表

题目描述

设 A 和 B 是两个带头结点的单链表，其中元素递增有序且无重复元素。设计一个算法从 A 和 B 中的公共元素产生单链表 C，要求不破坏 A、B 的结点。

解题代码

ListNode* generateList(ListNode* head1, ListNode* head2) {
    ListNode* head3 = new ListNode(-1);
    ListNode* curNode = head3;
    head1 = head1->next;
    head2 = head2->next;
    while (head1 != nullptr && head2 != nullptr) {
        if (head1->val == head2->val) {
            curNode->next = new ListNode(head1->val);
            curNode = curNode->next;
            head1 = head1->next;
            head2 = head2->next;
        }
        else if (head1->val > head2->val) {
            head2 = head2->next;
        }
        else {
            head1 = head1->next;
        }
    }
    return head3;
}

两链表的交集

题目描述

已知两个带头节点的单链表 A 和 B 分别表示两个集合，其元素递增排列且无重复元素。编制函数，求 A 和 B 的交集，存放于 A 链表中，并释放多余的结点。

解题代码

void listIntersection(ListNode* head1, ListNode* head2) {
    ListNode* curNode1 = head1->next;
    ListNode* curNode2 = head2->next;
    ListNode* preNode = head1;
    while (curNode1 != nullptr && curNode2 != nullptr) {
        if (curNode1->val == curNode2->val) {
            preNode->next = curNode1;
            preNode = preNode->next;
            curNode1 = curNode1->next;
            ListNode* tempNode = curNode2;
            curNode2 = curNode2->next;
            delete tempNode;
        }
        else if (curNode1->val > curNode2->val) {
            ListNode* tempNode = curNode2;
            curNode2 = curNode2->next;
            delete tempNode;
        }
        else {
            ListNode* tempNode = curNode1;
            curNode1 = curNode1->next;
            delete tempNode;
        }
    }
    // 释放剩余结点
    while (curNode1 != nullptr) {
        ListNode* tempNode = curNode1;
        curNode1 = curNode1->next;
        delete tempNode;
    }
    while (curNode2 != nullptr) {
        ListNode* tempNode = curNode2;
        curNode2 = curNode2->next;
        delete tempNode;
    }
    preNode->next = nullptr;
}

判断连续子序列

题目描述

两个整数序列 A = a1, a2, a3, …, am 和 B = b1, b2, b3, …, bn 已经存入两个带头结点单链表中，设计一个算法，判断序列 B 是否是序列 A 的连续子序列。

解题代码

bool isSubsequence(ListNode* head1, ListNode* head2) {
    ListNode* startNode = head1->next;
    ListNode* curNode1 = startNode;
    ListNode* curNode2 = head2->next;
    while (curNode1 != nullptr && curNode2 != nullptr) {
        if (curNode1->val == curNode2->val) {
            curNode1 = curNode1->next;
            curNode2 = curNode2->next;
        }
        else {
            startNode = startNode->next;
            curNode1 = startNode;
            curNode2 = head2->next;
        }
    }
    return curNode2 == nullptr;
}

判断链表环路

题目描述

单链表有环，是指单链表的最后一个结点的指针指向了链表的某个结点（通常单链表的最后一个结点的指针域是空的）。试编写算法判断不带头结点的单链表是否存在环。

解题代码

哈希表

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> nodeSet;
    while (head != nullptr) {
        if (nodeSet.count(head) > 0) {
            return true;
        }
        nodeSet.emplace(head);
        head = head->next;
    }
    return false;
}

快慢指针

bool hasCycle(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }
    ListNode* slow = head; // 每次走一步
    ListNode* fast = head; // 如果可能，每次走两步
    while (slow != nullptr && fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
        if (fast != nullptr) {
            fast = fast->next;
        }
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

查找倒数第k个结点

题目描述

已知一个带有头结点的单链表，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置的结点（k 为正整数）。若查找成功，算法输出该结点的值，并返回 1；否则，只返回 0.

解题代码

bool lastKthNode(ListNode* head, int k) {
    ListNode* curNode1 = head->next;
    // 先将curNode1移动到第k个结点
    for (int i = 0; i < k; ++i) { 
        if (curNode1 != nullptr) {
            curNode1 = curNode1->next;
        }
        else {
            return false;
        }
    }
    ListNode* curNode2 = head->next;
    // 当curNode1到达末尾，curNode2位于倒数第k个结点
    while (curNode1 != nullptr) {
        curNode1 = curNode1->next;
        curNode2 = curNode2->next;
    }
    cout << curNode2->val << endl;
    return true;
}

重排链表

题目描述

设线性表 L = (a1, a2, a3, …, an-2, an - 1, an) 采用带头结点的单链表保存，请设计一个空间复杂度为 O(1) 且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L’ = (a1, an, a2, an - 1, a3, an - 2, …)。

解题代码

// 中间结点
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next;
        if (fast->next != nullptr) {
            fast = fast->next;
        }
    }
    return slow;
}
// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* preNode = nullptr;
    ListNode* curNode = head;
    while (curNode != nullptr) {
        ListNode* tempNode = curNode->next;
        curNode->next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
}
// 归并链表
void mergeList(ListNode* l1, ListNode* l2) {
    while (l1 != nullptr && l2 != nullptr) {
        ListNode* l1Next = l1->next;
        ListNode* l2Next = l2->next;
        l1->next = l2;
        l1 = l1Next;
        l2->next = l1;
        l2 = l2Next;
    }
}
// 重排链表
void reorderList(ListNode* head) {
    ListNode* l1 = head->next;
    ListNode* mid = middleNode(l1);
    ListNode* l2 = mid->next;
    mid->next = nullptr;
    l2 = reverseList(l2);
    mergeList(l1, l2);
}