【数据结构】链表 & 树，你也被绕晕了？不妨来这看看

1、链表

大多数链表类的算法题，引入一个虚拟头结点可以极大的降低复杂度。
如果操作比较复杂，不要吝啬临时变量，多用几个指针标记就会清晰很多。
总体来说链表类的题还是挺复杂的，指针指来指去非常容易晕，还是需要多练。

环形链表

Leetcode——环形链表

快慢指针法： 快指针和慢指针初始时指向头节点，当快指针指向和快指针指向节点内的next指针不为空时，快指针一次走两步，慢指针一次走一步，快指针入环后走N圈后慢指针入环，当快指针和慢指针相等时说明存在环，如果出循环则说明不存在环。

关键的地方是快指针一次走两步，慢指针一次走一步，如果存在环则快指针和慢指针一定会相遇。为什么一定会相遇呢？如果存在环，假设当慢指针入环时快指针距离此时慢指针的位置为N，则接下来每当快指针追赶慢指针一次，它们的距离就减一，直到减为0，此时快慢指针就相遇了。

代码语言：javascript代码运行次数：0运行复制

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head, *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}

环形链表 II

Leetcode——环形链表 II

还是快慢指针，当快慢指针相遇时我们让meet指针指向相遇时的节点，然后让头指针head和meet指针一步步地向后走，当两指针相遇时指向的节点就是链表开始入环的第一个节点。为什么这两个指针一定会相遇在链表开始入环的第一个节点？

假设头指针距离链表开始入环的第一个节点的长度为L，meet指针相距链表开始入环的第一个节点的距离是N，环的长度为C，当慢指针入环时快指针走了x圈，因为快指针的速度是慢指针的2倍，那我们可以得到下面的等式：

2(L + N) = L + X*C + N

化简得：L = X*C - N，由这个等式可以得出head和meet相遇是必然的。

代码语言：javascript代码运行次数：0运行复制

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head, *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            struct ListNode* meet = fast;
            while (head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

两个链表的第一个公共结点

两个链表的第一个公共结点

解法一：让长的链表先走差值次，再两个链表同步走。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		int len1 = 0, len2 = 0;
		ListNode* cur1 = pHead1, *cur2 = pHead2;
		while (cur1)
		{
			len1++;
			cur1 = cur1->next;
		}
		while (cur2)
		{
			len2++;
			cur2 = cur2->next;
		}
		if (len1 > len2) return func(pHead1, pHead2, len1 - len2);
		else return func(pHead2, pHead1, len2 - len1);
    }
	ListNode* func(ListNode* p1, ListNode* p2, int len)
	{
		while (len--) p1 = p1->next;
		while (p1)
		{
			if (p1 == p2) return p1;
			p1 = p1->next;
			p2 = p2->next;
		}
		return nullptr;
	}
};

解法二：让两个链表走相同多的路。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* cur1 = pHead1, *cur2 = pHead2;
		while (cur1 != cur2)
		{
			cur1 = cur1 == nullptr ? pHead2 : cur1->next;
			cur2 = cur2 == nullptr ? pHead1 : cur2->next;
		}
		return cur1;
    }
};

合并两个有序链表

合并两个有序链表

方法一：迭代。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newhead = new ListNode;
        ListNode* tail = newhead;
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 == nullptr ? list2 : list1;
        tail = newhead->next;
        delete newhead;
        return tail;
    }
};

方法二：递归。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        if (l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

两数相加

两数相加

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1, *cur2 = l2;
        ListNode* newhead = new ListNode; // 引入虚拟头结点方便操作
        ListNode* tail = newhead; // 指向新链表的最后一个节点
        int t = 0; // 处理进位
        while (cur1 || cur2 || t)
        {
            if (cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            tail->next = new ListNode(t % 10);
            tail = tail->next;
            t /= 10;
        }
        tail = newhead->next;
        delete newhead;
        return tail;
    }
};

两两交换链表中的节点

两两交换链表中的节点

方法一：递归。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = head->next;
        head->next = swapPairs(newhead->next);
        newhead->next = head;
        return newhead;
    }
};

方法二：引入虚拟头节点和尾指针，然后迭代。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = new ListNode;
        newhead->next = head;
        ListNode* cur = head, *tail = newhead;
        while (cur && cur->next)
        {
            ListNode* next = cur->next->next;
            cur->next->next = cur;
            tail->next = cur->next;
            cur->next = next;
            tail = cur;
            cur = cur->next;
        }
        tail = newhead->next;
        delete newhead;
        return tail;
    }
};

方法三：不要吝啬变量，用指针标记直到过程清晰为止，此时顺序什么的就不用太担心了。ps：我多用点变量怎么了？让别人看见还以为我用不起呢。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = new ListNode;
        newhead->next = head;
        ListNode* tail = newhead, *cur = head, *next = cur->next, *nnext = next->next;
        while (cur && cur->next)
        {
            tail->next = next;
            next->next = cur;
            cur->next = nnext;

            tail = cur;
            cur = nnext;
            if (cur) next = cur->next;
            if (next) nnext = next->next;
        }
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};

重排链表

重排链表

分三步走，算是三个小问题的综合应用。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        // 1.将链表从中间分开
        ListNode* fast = head, *slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 2.将后半部分逆序
        ListNode* newhead1 = new ListNode;
        ListNode* cur = slow->next;
        slow->next = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead1->next;
            newhead1->next= cur;
            cur = next;
        }
        // 3.一前一后合并
        ListNode* newhead2 = new ListNode;
        ListNode* tail = newhead2, *cur1 = head, *cur2 = newhead1->next;
        while (cur1)
        {
            tail->next = cur1;
            cur1 = cur1->next;
            tail = tail->next;
            if (cur2)
            {
                tail->next = cur2;
                cur2 = cur2->next;
                tail = tail->next;
            }
        }
        delete newhead1;
        delete newhead2;
    }
};

合并 K 个升序链表 *

合并 K 个升序链表

方法一：优先级队列。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for (auto &e : lists) 
            if (e) pq.push(e);
        ListNode* newhead = new ListNode;
        ListNode* tail = newhead;
        while (pq.size())
        {
            tail->next = pq.top();
            pq.pop();
            tail = tail->next;
            if (tail->next) pq.push(tail->next);
        }
        tail = newhead->next;
        delete newhead;
        return tail;
    }
};

方法二：分治。其实分治的做法很简单，只需要把vector中的链表一分为二，左右分别分治，然后就变成了合并两个有序链表的过程。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
    ListNode* merge(vector<ListNode*>& lists, int l, int r)
    {
        if (l > r) return nullptr;
        if (l == r) return lists[l];
        int mid = (l + r) >> 1;
        // 左右分治
        ListNode* l1 = merge(lists, l, mid);
        ListNode* l2 = merge(lists, mid + 1, r);
        // 合并两个有序链表
        ListNode* newhead = new ListNode;
        ListNode* tail = newhead;
        ListNode* cur1 = l1, *cur2 = l2;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }
        if (cur1) tail->next = cur1;
        if (cur2) tail->next = cur2;
        tail = newhead->next;
        delete newhead;
        return tail; 
    }
};

既然分治之后就变成了合并两个有序链表，那自然也可以用递归，过程更简洁。
方法三：分治+递归。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
    ListNode* merge(vector<ListNode*>& lists, int l, int r)
    {
        if (l > r) return nullptr;
        if (l == r) return lists[l];
        int mid = (l + r) >> 1;
        return merge2Lists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    ListNode* merge2Lists(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        if (l1->val < l2->val)
        {
            l1->next = merge2Lists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

K 个一组翻转链表 *

K 个一组翻转链表

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        int len = 0; 
        while (cur)
        {
            len++;
            cur = cur->next;
        }
        len /= k; // 可以翻转len组
        cur = head;
        ListNode* newhead = new ListNode;
        ListNode* tail = newhead;
        for (int i = 0; i < len; i++)
        {
            ListNode* tmp = cur; // 标记翻转后的尾节点
            for (int j = 0; j < k; j++)
            {
                ListNode* next = cur->next;
                cur->next = tail->next;
                tail->next = cur;
                cur = next;
            }
            tail = tmp; // 更新尾节点
        }
        tail->next = cur; // 将可能剩余的拼接到后面
        tail = newhead->next;
        delete newhead;
        return tail;
    }
};

2、树

判断二叉树是否是完全二叉树

牛客——判断是不是完全二叉树

层序遍历二叉树，当某次pop到非节点时不再入节点，然后不断pop，如果是完全二叉树，则pop到的全是非节点；如果是非完全二叉树，则某次会pop到节点。

完全二叉树：

非完全二叉树：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if (root == nullptr)
        {
            return true;
        }
        _qu.push(root);
        while (!_qu.empty())
        {
            TreeNode* front = _qu.front();
            _qu.pop();
            if (front == nullptr)
            {
                break;
            }
            _qu.push(front->left);
            _qu.push(front->right);
        }
        while (!_qu.empty())
        {
            TreeNode* front = _qu.front();
            _qu.pop();
            if (front != nullptr)
            {
                return false;
            }
        }
        return true;
    }
private:
    queue<TreeNode*> _qu;
};

二叉树的前序遍历

Leetcode——二叉树的前序遍历

每次递归都会建立新的栈帧空间，不同的栈帧空间内相同的变量之间互不影响，而我们需要的是每次函数递归都要改变下标，所以需要传地址。

代码语言：javascript代码运行次数：0运行复制

int TreeSize(struct TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* arr, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    //每次递归都会建立新的栈帧空间，不同的栈帧空间内相同的变量之间互不影响，
    //而我们需要的是每次函数递归都要改变下标，所以需要传地址。
    arr[(*pi)++] = root->val;
    PreOrder(root->left, arr, pi);
    PreOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    int* arr = (int*)malloc(*returnSize * sizeof(int));
    int i = 0;
    PreOrder(root, arr, &i);
    return arr;
}

翻转二叉树

Leetcode——翻转二叉树

经典的递归问题，先从叶子结点开始反转，然后回归，深度优先搜索。

代码语言：javascript代码运行次数：0运行复制

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL)
    {
        return NULL;
    }
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2025-04-04，如有侵权请联系 cloudcommunity@tencent 删除二叉树数据结构递归链表指针

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始

【数据结构】链表 & 树，你也被绕晕了？不妨来这看看