c++链表问题汇总(代码及解析)

女爷i 2024-04-17 21:50 81阅读 0赞

**目录**

一、链表与指针

1.1 单向双向表

1.2 数组指针

1.3 链表的合并

二、链表应用汇总

2.1 链表中的值倒序

2.2 链表的倒数第k个节点

2.3 反转链表

2.4 链表的公共节点

2.5 链表环的入口节点

三、复杂链表的复制

3.1 题干

3.2 思路及注意事项

3.3 正确答案

3.4 错误代码找错

四、二叉树转为双向链表

--------------------

相应oj链接：

[https://www.nowcoder.com/ta/coding-interviews][https_www.nowcoder.com_ta_coding-interviews]

# **一、链表与指针** #

## **1.1** **单向双向表** ##

设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（  ）存储方式最节省运算时间

正确答案: D

*  单向链表
 *  单向循环链表
 *  双向链表
 *  双向循环链表

迅速从表头到表尾，单向链表于单向循环链表显然不行，双向不循环也不行，最快还是双向循环。

## **1.2** **数组指针** ##

下面代码会输出  ？。

int a[4] = { 1, 2, 3, 4 };
        cout << sizeof(a) << endl;
        int *ptr = (int*)(&a + 1);
        printf("%d", *(ptr - 1));

解析：

*  &a+1是整个数组的指向棏下一个地址，
 *  ptr-1 就是从下一个地址（随机地址）回到数组的最后一个数存储的地方
 *  &a + 1: 取数组a 的首地址，该地址的值加上sizeof(a) 的值，即&a + 4\*sizeof(int)，也就是下一个数组的首地址，显然当前指针已经越过了数组的界限。
 *  (int \*)(&a+1): 则是把上一步计算出来的地址，强制转换为int \* 类型，赋值给ptr。
 *  \*(a+1): a,&a 的值是一样的，但意思不一样，a 是数组首元素的首地址，也就是a\[0\]的首地址，&a 是数组的首地址，a+1 是数组下一元素的首地址，即a\[1\]的首地址,&a+1 是下一个数组的首地址。所以输出2
 *  \*(ptr-1): 因为ptr 是指向a\[3\]，并且ptr 是int \* 类型，所以\*(ptr-1) 是指向a\[3\] ，

经过在编译器编译之后，输出为

16
    4

## **1.3** **链表的合并** ##

已知两个链表list1 和list2 内的数据都是有序的，请把它们合并成一个链表，保持里面的数据依然有序，要求用递归的方法实现()。下面是定义的链表的节点：

struct Node {
    	int data;
    	Node *next;
    };
    typedef struct Node Node;

请写出函数Node \* MergeRecursive(Node \*head1, Node \*head2)的实现。

解析：运用递归实现了链表的合并，回归表头，其他部分对更小的值进行递归。

程序作用就是，

*  如果两个head指向的都有值，则返回指向值小的head，这个head指向的值往下递归
 *  如果一个head为NULL，则返回另一个head。这部分适用于程序结束时候的情况。即出现这种情况递归就结束了。

Node * MergeRecursive(Node *head1, Node *head2)
    {
    	if (head1 == NULL)
    		return head2;
    	if (head2 == NULL)
    		return head1;
    	Node *head = NULL;
    	if (head1->data < head2->data){
    		head = head1;
    		head->next = MergeRecursive(head1->next, head2);
    	}
    	else {
    		head = head2;
    		head->next = MergeRecursive(head1, head2->next);
    	}
    	return head;
    }

# **二、链表应用汇总** #

## **2.1** **链表中的值倒序** ##

/**
    *  struct ListNode {
    *        int val;
    *        struct ListNode *next;
    *        ListNode(int x) :
    *              val(x), next(NULL) {
    *        }
    *  };
    */
    class Solution {
    public:
        vector<int> printListFromTailToHead(ListNode* head) {
            ListNode* node_ptr=head;
            vector<int> val_vector;
            for( ; node_ptr!=NULL; node_ptr=node_ptr->next){
                val_vector.insert(val_vector.begin(),node_ptr->val);
            }
            // reverse vector
            return val_vector;
        }
    };

难度不难，但是需要对vector这个工具进行熟练运用。

比如insert命令是从前面插入。

然后就是链表的遍历。

## **2.2** **链表的倒数第k个节点** ##

输入一个链表，输出该链表中倒数第k个结点。

**倒数第k个节点c++**

思路清晰即可

/*
    struct ListNode {
            int val;
            struct ListNode *next;
            ListNode(int x) :
                            val(x), next(NULL) {
            }
    };*/
    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            if(pListHead==NULL)return NULL;
            int list_size=0;
            ListNode* node_ptr=pListHead;
            while(node_ptr!=NULL){
                node_ptr=node_ptr->next;
                list_size++;
            }
            int idx_back_k=list_size-k;
            if(idx_back_k<0)return NULL;
            node_ptr=pListHead;
            for(int idx=0;idx<idx_back_k;idx++){
                node_ptr=node_ptr->next;
            }
            return node_ptr;
        }
    };

可以采用剑指offer中的快慢指针来解，即快指针指向慢指针之后的k位，一起向后遍历，快指针指向NULL的时候，慢指针刚好在倒数第k个节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70][]

另外，需要注意程序鲁棒性，即链表不够k位的情况。这种方法应该是最简单的方法了。

class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            ListNode* fast_ptr=pListHead;
            ListNode* slow_ptr=pListHead;
            for(int idx=0;idx<k;idx++){
                if(fast_ptr==NULL)return NULL;
                fast_ptr=fast_ptr->next;
            }
            while(fast_ptr!=NULL){
                fast_ptr=fast_ptr->next;
                slow_ptr=slow_ptr->next;
            }
            return slow_ptr;
        }
    };

## **2.3** **反转链表** ##

反转链表需要将之前的链表进行反转。因为内存限制，c++代码最好不要引入新的变量。数据结构的题，有必要画出相应的图方便不出错与理解。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1][]

一定要考虑程序鲁棒性，即如果空链表的话，返回NULL，不要直接return。

并且需要少量的内存占用，尽量运用已有的节点。

/*
    struct ListNode {
            int val;
            struct ListNode *next;
            ListNode(int x) :
                            val(x), next(NULL) {
            }
    };*/
    class Solution {
    public:
        ListNode* ReverseList(ListNode* pHead) {
            if(pHead==NULL)return NULL;
            ListNode* pre_node=new ListNode(pHead->val);
            ListNode* cur_node=pHead->next;
            ListNode* next_node=cur_node;
            while(next_node!=NULL){
                next_node=cur_node->next;
                cur_node->next=pre_node;
                pre_node=cur_node;
                cur_node=next_node;
            }
            return pre_node;
        }
    };

## **2.4** **链表的第一个公共节点** ##

找到两个链表公共节点，思路清晰即可，注意非void函数一定要返回值。且第一个链表固定一个节点时候，第二个链表需要从头开始。两次遍历，找到公共节点。但是此方法并不是最简单的方法。

### 方法一、从后往前对比： ###

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            if(pHead1==NULL||pHead2==NULL)return NULL;
            ListNode* node_1=pHead1;
            ListNode* node_2;
            while(node_1!=NULL){
                node_2=pHead2;
                while(node_2!=NULL){
                    if(node_1==node_2)return node_1;
                    node_2=node_2->next;
                }
                node_1=node_1->next;
            }
            return NULL;
        }
    };

### 方法二、辅助存储，需要存储栈 ###

最简单的方法，相当于将两个链表存入栈中，来实现：

要注意，pop的时候一定要确定 !stack.empty()

class Solution {
    public:
    	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
    		if (pHead1 == NULL || pHead2 == NULL)return NULL;
    		stack<ListNode*> node1;
    		stack<ListNode*> node2;
    		ListNode* node_ptr = pHead1;
    		while (node_ptr != NULL){
    			node1.push(node_ptr);
    			node_ptr = node_ptr->next;
    		}
    		node_ptr = pHead2;
    		while (node_ptr != NULL){
    			node2.push(node_ptr);
    			node_ptr = node_ptr->next;
    		}
    		while (!node1.empty() && !node2.empty()&&node1.top() == node2.top() ){
    			node_ptr = node1.top();
    			node1.pop();
    			node2.pop();
    		}
    		return node_ptr;
    	}
    };

### 方法三，最简单方法 ###

统计出来链表的长度，不需要辅助存储。结尾的NULL往前依次对齐。

## **2.5** **链表环的入口节点** ##

链表其中包含环，如果有环则输出入口节点，没有则输出NULL

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 2][]

需要一快一慢两个指针，相遇则表明有环。可以通过环中的节点判断环的大小。

class Solution {
    public:
            // fast ptr and slow ptr find meeting node
            ListNode* meeting_node(ListNode* pHead){
                    if (pHead == NULL)return NULL;
                    ListNode* fast_ptr = pHead->next;
                    ListNode* slow_ptr = pHead;
                    while (fast_ptr != slow_ptr){
                            if (fast_ptr == NULL)return NULL;
                            fast_ptr = fast_ptr->next;
                            if (fast_ptr == NULL)return NULL;
                            fast_ptr = fast_ptr->next;
                            slow_ptr = slow_ptr->next;
                    }
                    return fast_ptr;
            }
    // entry node
            ListNode* EntryNodeOfLoop(ListNode* pHead)
            {
                    ListNode* meet_node_ptr = meeting_node(pHead);
                    if (meet_node_ptr == NULL)return NULL;
    ListNode* fast_ptr = meet_node_ptr->next;
                    ListNode* entry_node = pHead->next;
                    while (fast_ptr != meet_node_ptr){
                            fast_ptr = fast_ptr->next;
                            entry_node = entry_node->next;
                    }
    fast_ptr = pHead;
                    while (fast_ptr != entry_node){
                            fast_ptr = fast_ptr->next;
                            entry_node = entry_node->next;
                    }
                    return entry_node;
            }
    };

# 三、复杂链表的复制 #

OJ：[https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_f836b2c43afc4b35ad6adc41ec941dba_tpId_13_tqId_11178_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

## 3.1 题干 ##

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

## 3.2 思路及注意事项 ##

首先，把新链表复制到旧链表的结尾

然后，复制randm指针（注意，random指针可能为NULL的情况出现）

最后，把链表拆开。

## 3.3 正确答案 ##

分开用子函数实现：

class Solution {
    public:
    	//void CloneNodes(RandomListNode *);
    	//void ConnectRandomNodes(RandomListNode* );
    	//RandomListNode* ReconnectNodes(RandomListNode* );
    	RandomListNode* Clone(RandomListNode* pHead)
    	{
    		if (pHead == nullptr)
    			return NULL;
    		CloneNodes(pHead);
    		ConnectRandomNodes(pHead);
    		return ReconnectNodes(pHead);
    
    	}
    	void CloneNodes(RandomListNode *Head)
    	{
    		RandomListNode* pNode = Head;
    		while (pNode != nullptr)
    		{
    			RandomListNode* pCloned = new RandomListNode(pNode->label);
    			//pCloned->label=pNode->label;
    			pCloned->next = pNode->next;
    			pCloned->random = nullptr;
    
    			pNode->next = pCloned;
    			pNode = pCloned->next;
    		}
    	}
    	void ConnectRandomNodes(RandomListNode* Head)
    	{
    		RandomListNode* pNode = Head;
    		while (pNode != nullptr)
    		{
    			RandomListNode* pCloned = pNode->next;
    			if (pNode->random != nullptr)
    			{
    				pCloned->random = pNode->random->next;
    			}
    			pNode = pCloned->next;
    		}
    	}
    	RandomListNode* ReconnectNodes(RandomListNode* Head)
    	{
    		RandomListNode *pNode = Head;
    		RandomListNode *result = Head->next;
    		while (pNode != NULL)
    		{
    			RandomListNode *pClone = pNode->next;
    			pNode->next = pClone->next;
    			pNode = pNode->next;
    			if (pNode != NULL)
    				pClone->next = pNode->next;
    
    		}
    		return result;
    	}
    
    };

合并实现：

class Solution {
    public:
    	RandomListNode* Clone(RandomListNode* pHead)
    	{
    		if (!pHead) return NULL;
    		RandomListNode *cur = pHead;
    		while (cur){
    			RandomListNode *node = new RandomListNode(cur->label);
    			node->next = cur->next;
    			cur->next = node;
    			cur = node->next;
    		}//直到cur指向了原先链表的结尾null处
    		cur = pHead;
    		RandomListNode *p;
    		while (cur){
    			p = cur->next;
    			if (cur->random){
    				p->random = cur->random->next;
    
    			}
    			cur = p->next;
    		}
    
    		RandomListNode *pCloneHead = pHead->next;
    		RandomListNode *tmp;
    		cur = pHead;
    		while (cur->next){
    			tmp = cur->next;
    			cur->next = tmp->next;
    			cur = tmp;
    		}
    		return pCloneHead;
    	}
    };

个人编写正确的答案

class Solution {
    public:
    	void simple_clone(RandomListNode* pHead){
    		RandomListNode* old_ptr = pHead;
    		while (old_ptr != NULL){
    			RandomListNode* new_ptr = new RandomListNode(old_ptr->label);
    			new_ptr->next = old_ptr->next;
    			old_ptr->next = new_ptr;
    			old_ptr = new_ptr->next;
    		}
    	}
    	void clone_random(RandomListNode* pHead){
    		RandomListNode* old_ptr = pHead;
    		while (old_ptr != NULL){
    			RandomListNode* new_ptr = old_ptr->next;
    			if (old_ptr->random != NULL){
    				new_ptr->random = old_ptr->random->next;
    			}
    			old_ptr = new_ptr->next;
    		}
    	}
    	RandomListNode* split(RandomListNode* pHead){
    		RandomListNode* old_ptr = pHead;
    		RandomListNode* new_head = pHead->next;
    		RandomListNode* new_ptr = new_head;
    		while (new_ptr->next != NULL){
    			old_ptr->next = new_ptr->next;
    			old_ptr = old_ptr->next;
    			new_ptr->next = old_ptr->next;
    			new_ptr = new_ptr->next;
    		}
    		new_ptr->next = NULL;
    		old_ptr->next = NULL;
    		return new_head;
    	}
    
    	RandomListNode* Clone(RandomListNode* pHead)
    	{
    		if (pHead == NULL)return NULL;
    		//simple clone
    		simple_clone(pHead);
    		clone_random(pHead);
    		return split(pHead);
    	}
    };

## 3.4 错误代码找错 ##

下面代码找错误：提醒，用oj会出现堆栈溢出

#include<vector>
    #include<iostream>
    using namespace std;
    
    
    struct RandomListNode {
    	int label;
    	struct RandomListNode *next, *random;
    	RandomListNode(int x) :
    		label(x), next(NULL), random(NULL) {
    	}
    };
    
    class Solution {
    public:
    	void simple_append_clone(RandomListNode* pHead){
    		if (pHead == NULL)return;
    		RandomListNode* old_node = pHead;
    
    		while (old_node != NULL){
    			RandomListNode* new_node = new RandomListNode(old_node->label);
    			new_node->next = old_node->next;
    			old_node->next = new_node;
    			old_node = new_node->next;
    		}
    	}
    
    	void clone_random(RandomListNode* pHead){
    		if (pHead == NULL)return;
    		RandomListNode* old_node = pHead;
    
    		while (old_node != NULL){
    			if (old_node->random != NULL)old_node->next->random = old_node->random->next;
    			old_node = old_node->next->next;
    		}
    	}
    
    	RandomListNode* divide(RandomListNode* pHead){
    		if (pHead == NULL)return NULL;
    		RandomListNode* new_head = pHead->next;
    		RandomListNode* new_node = new_head;
    		RandomListNode* old_node = pHead;
    		while (new_node->next != NULL){
    			new_node = old_node->next;
    			old_node->next = old_node->next->next;
    			old_node = old_node->next;
    			if (new_node->next != NULL){
    				new_node->next = new_node->next->next;
    				new_node = new_node->next;
    			}
    		}
    		return new_head;
    	}
    
    	RandomListNode* Clone(RandomListNode* pHead)
    	{
    		if (pHead == NULL)return NULL;
    		simple_append_clone(pHead);
    		clone_random(pHead);
    		return divide(pHead);
    	}
    };
    
    int main(){
    	Solution Solution;
    	vector<int> rating;
    	int num; cin >> num;
    	while (num--){
    		int rate; cin >> rate;
    		rating.push_back(rate);
    	}
    
    	int end; cin >> end;
    	return 0;
    }

改正方法：把第三个函数最终的判断删掉，加上两个指针都指向NULL，表示到了结尾

# 四、二叉树转为双向链表 #

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

中序遍历即可，多一个记录pre的指针

class Solution {
    public:
    	TreeNode* Convert(TreeNode* pRootOfTree)
    	{
    		if (pRootOfTree == nullptr) return nullptr;
    		TreeNode* pre = nullptr;
    
    		convertHelper(pRootOfTree, pre);
    
    		TreeNode* res = pRootOfTree;
    		while (res->left)
    			res = res->left;
    		return res;
    	}
    
    	void convertHelper(TreeNode* cur, TreeNode*& pre)
    	{
    		if (cur == nullptr) return;
    		convertHelper(cur->left, pre);
    
    		cur->left = pre;
    		if (pre) pre->right = cur;
    		pre = cur;
    		convertHelper(cur->right, pre);
    	}
    };

来自 <https://www.nowcoder.com/profile/3900945/codeBookDetail?submissionId=16370979>

或者：
    class Solution {
    public:
        void ConvertNode(TreeNode* pNode, TreeNode** pLastNodeInList){
            if (pNode == nullptr)
                return;
    
            //if(pNode->left!=nullptr)
            ConvertNode(pNode->left, pLastNodeInList);
    
            pNode->left = *pLastNodeInList;
            if (*pLastNodeInList != nullptr)
                (*pLastNodeInList)->right = pNode;
            *pLastNodeInList = pNode;
    
            //if(pNode->right!=nullptr)
            ConvertNode(pNode->right, pLastNodeInList);
        }
    
        TreeNode* Convert(TreeNode* pRootOfTree)
        {
            TreeNode* pLastNodeInList = nullptr;
            ConvertNode(pRootOfTree, &pLastNodeInList);
    
            TreeNode* pHeadOfList = pLastNodeInList;
            while (pHeadOfList != nullptr&&pHeadOfList->left != nullptr){
                pHeadOfList = pHeadOfList->left;
            }
    
            return pHeadOfList;
        }
    };

来自 <https://www.nowcoder.com/profile/349656/codeBookDetail?submissionId=17180119>

[https_www.nowcoder.com_ta_coding-interviews]: https://www.nowcoder.com/ta/coding-interviews
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/169169a1d218415a8eb4ea2e42b54a82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/5af425cdc5aa4d9aa7083fe6f87d0046.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e3dd099bc318436ca2fb7c249cd35747.png
[https_www.nowcoder.com_practice_f836b2c43afc4b35ad6adc41ec941dba_tpId_13_tqId_11178_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking