链表简单题

面试题 02.03. 删除中间节点

难度简单173收藏分享切换为英文接收动态反馈

若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。

假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。

例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

示例：

输入：节点 5 （位于单向链表 4->5->1->9 中）
输出：不返回任何数据，从链表中删除传入的节点 5，使链表变为 4->1->9

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode *node) {
        // 把后一个节点赋给当前节点，然后删除后一个节点
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

1290. 二进制链表转整数

难度简单136收藏分享切换为英文接收动态反馈

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

示例 2：

输入：head = [0]
输出：0

示例 3：

输入：head = [1]
输出：1

示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880

示例 5：

输入：head = [0,0]
输出：0

提示：

链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

class Solution {
public:
    int getDecimalValue(ListNode *head) {
        int res = 0;
        while (head != nullptr) {
            res <<= 1;
            res += head->val;
            head = head->next;
        }
        return res;
    }
};

剑指 Offer 22. 链表中倒数第k个节点

难度简单421收藏分享切换为英文接收动态反馈

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

class Solution {
public:
    ListNode *getKthFromEnd(ListNode *head, int k) {
        ListNode *slow = head;
        ListNode *fast = head;
        // 快指针先走k步
        while (k > 0) {
            k--;
            fast = fast->next;
        }
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

剑指 Offer II 024. 反转链表

难度简单109收藏分享切换为英文接收动态反馈

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        // 递归
        if (head == nullptr || head->next == nullptr) return head;
        ListNode *last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
/*        // 迭代
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;*/
    }
};

剑指 Offer 06. 从尾到头打印链表

难度简单359收藏分享切换为英文接收动态反馈

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

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

限制：

0 <= 链表长度 <= 10000

class Solution {
public:
    vector<int> reversePrint(ListNode *head) {
        vector<int> res;
        recursive(head, res);
        return res;
    }

    void recursive(ListNode *head, vector<int> &res) {
        if (head == nullptr) return;
        // 递归就是压栈的过程
        recursive(head->next, res);
        res.push_back(head->val);
    }
};

剑指 Offer 25. 合并两个排序的链表

难度简单305收藏分享切换为英文接收动态反馈

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
/*        // 常规做法
        ListNode head;
        ListNode *cur = &head;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1 != nullptr)
            cur->next = l1;
        if (l2 != nullptr)
            cur->next = l2;
        return head.next;*/
        return recursive(l1, l2);
    }

    // 递归
    ListNode *recursive(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        if (l1->val < l2->val) {
            l1->next = recursive(l1->next, l2);
            return l1;
        } else {
            l2->next = recursive(l1, l2->next);
            return l2;
        }
    }
};

876. 链表的中间结点

难度简单765收藏分享切换为英文接收动态反馈

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

class Solution {
public:
    ListNode *middleNode(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

剑指 Offer II 023. 两个链表的第一个重合节点

难度简单61收藏分享切换为英文接收动态反馈

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int l1 = countLength(headA);
        int l2 = countLength(headB);
        ListNode *longList = l1 > l2 ? headA : headB;
        ListNode *shortList = l1 > l2 ? headB : headA;

        int temp = std::abs(l1 - l2);
        while (temp > 0) {
            longList = longList->next;
            temp--;
        }

        while (longList != nullptr) {
            if (longList == shortList) return longList;
            longList = longList->next;
            shortList = shortList->next;
        }
        return nullptr;
    }

    // 计算链表长度
    int countLength(ListNode *head) {
        int res = 0;
        while (head != nullptr) {
            head = head->next;
            res++;
        }
        return res;
    }

};

面试题 02.01. 移除重复节点

难度简单174收藏分享切换为英文接收动态反馈

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]

示例2:

 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]

提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

class Solution {
public:
    ListNode *removeDuplicateNodes(ListNode *head) {
        if (head == nullptr) return nullptr;
        
        ListNode *cur = head;
        unordered_set<int> set;
        set.emplace(head->val);

        while (cur->next != nullptr) {
            if (set.find(cur->next->val) != set.end()) {
                // 已有
                cur->next = cur->next->next;
            } else {
                // 新元素
                set.emplace(cur->next->val);
                cur = cur->next;
            }
        }
        return head;
    }
};

面试题 17.12. BiNode

难度简单128收藏分享切换为英文接收动态反馈

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

提示：

节点数量不会超过 100000。

class Solution {
public:
//    TreeNode *res = nullptr;
//    TreeNode *pre = nullptr;
//
//    TreeNode *convertBiNode(TreeNode *root) {
//        inorder(root);
//        return res;
//    }
//
//    void inorder(TreeNode *root) {
//        if (root == nullptr) return;
//        inorder(root->left);
//        // 找到链表头节点
//        if (res == nullptr) res = root;
//        root->left = nullptr;
//        // 上个节点的右指针指向当前节点
//        if (pre != nullptr) pre->right = root;
//        pre = root;
//        inorder(root->right);
//    }

    TreeNode *convertBiNode(TreeNode *root) {
        stack<TreeNode *> stk;
        TreeNode *res = nullptr;
        TreeNode *pre = nullptr;
        while (!stk.empty() || root != nullptr) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            root->left = nullptr;
            if(res == nullptr) res = root;
            if(pre != nullptr) pre->right = root;
            pre = root;
            root = root->right;
        }
        return res;
    }
};

剑指 Offer II 027. 回文链表

难度简单93收藏分享切换为英文接收动态反馈

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

输入: head = [1,2]
输出: false

提示：

链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

class Solution {
public:
    bool isPalindrome(ListNode *head) {
        if (head->next == nullptr) return true;
        ListNode *mid = findMid(head);
        ListNode *cur = reverse(mid);
        while (cur != nullptr) {
            if (head->val != cur->val) return false;
            head = head->next;
            cur = cur->next;
        }
        return true;
    }

    // 反转链表
    ListNode *reverse(ListNode *head) {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 找中间节点
    ListNode *findMid(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

剑指 Offer 18. 删除链表的节点

难度简单274收藏分享切换为英文接收动态反馈

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

class Solution {
public:
    ListNode *deleteNode(ListNode *head, int val) {
        ListNode newHead;
        newHead.next = head;

        ListNode *cur = &newHead;
        while (cur->next != nullptr) {
            if (cur->next->val == val) {
                cur->next = cur->next->next;
                return newHead.next;
            }
            cur = cur->next;
        }

        return newHead.next;
    }
};

203. 移除链表元素

难度简单1144收藏分享切换为英文接收动态反馈

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

class Solution {
public:
    ListNode *removeElements(ListNode *head, int val) {
        ListNode newHead;
        newHead.next = head;

        ListNode *cur = &newHead;
        while (cur->next != nullptr) {
            if (cur->next->val == val) {
                cur->next = cur->next->next;
                continue;
            }
            cur = cur->next;
        }

        return newHead.next;
    }
};

83. 删除排序链表中的重复元素

难度简单930收藏分享切换为英文接收动态反馈

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode res;
        res.next = head;
        ListNode *cur = head;
        while (cur != nullptr) {
            while (cur->next != nullptr && cur->val == cur->next->val) {
                cur->next = cur->next->next;
            }
            cur = cur->next;
        }

        return res.next;
    }
};

141. 环形链表

难度简单1724收藏分享切换为英文接收动态反馈

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return false;
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

标签：head,ListNode,cur,next,链表,简单,节点
From： https://www.cnblogs.com/sprinining/p/17070230.html

面试题 02.03. 删除中间节点

1290. 二进制链表转整数

剑指 Offer 22. 链表中倒数第k个节点

剑指 Offer II 024. 反转链表

剑指 Offer 06. 从尾到头打印链表

剑指 Offer 25. 合并两个排序的链表

876. 链表的中间结点

剑指 Offer II 023. 两个链表的第一个重合节点

面试题 02.01. 移除重复节点

面试题 17.12. BiNode

剑指 Offer II 027. 回文链表

剑指 Offer 18. 删除链表的节点

203. 移除链表元素

83. 删除排序链表中的重复元素

141. 环形链表

相关文章

赞助商

阅读排行