创建链表的过程详解

本人是一名刚开始学习算法的小白，今天遇到了一些关于链表的创建问题，查了一些资料，我把它们整理了一下，希望大家多多指教。

整体的代码：

#include<iostream>
using namespace std;struct Node {int val;Node* next;
};#创建
Node* creatlist(int n) {Node* Head=new Node;    //头节点 不存储数据Head->next = NULL;      Node* pre = Head;  //指向下一个节点的过渡值cout << "请依次输入" << n << "个链表的值:";for (int i = 0;i < n;i++) {Node* temp = new Node;cin >> temp->val;pre->next = temp;pre = temp;temp->next = NULL;	}return Head;
}#显示
void display(Node* head) {Node* temp=head->next;int e;cout << "该链表的遍历依次为：";while (temp!=NULL) {e = temp->val;cout << e << " ";temp = temp->next;}cout << "\n";
}int main() {int nums;cout << "请输入链表的长度:";cin >> nums;Node* head = creatlist(nums);display(head);return 0;
}

解释

1、基本概念：
链表是物体存储单元上不连续的储存结构，数据元素是由链表上的指针所连接。
每个节点都包含两部分：存储数据的数据域，和存储下一个节点的地址的指针域。

根据上图，利用数据结构struct建立一个节点：

struct Node {int val;    //数据域Node* next;  //指数域
};

创建链表：

#创建
Node* creatlist(int n) {//头节点 不存储数据，指针域指向空Node* Head=new Node;    Head->next = NULL; //为了让节点连接成链接，定义pre，最开始pre等于Head    Node* pre = Head;  cout << "请依次输入" << n << "个链表的值:";for (int i = 0;i < n;i++) {//每次循环都创建一个新的节点Node* temp = new Node;//把值赋给temp节点的数据域cin >> temp->val;//pre的指数域指向的下一个节点temp，把pre和temp连接起来pre->next = temp;//把temp节点赋给pre，重新定义prepre = temp;//在下次for循环再一次创建新temp节点前，temp的指数域指向空temp->next = NULL;	}//把头节点返回，知道头节点，节点与节点之间又相互连接，所以知道每个节点中的值return Head;
}

Node* pre 在这个程序中的作用是将不同节点连接成链接，
最开始pre等于head，pre的指数域指向temp1，然后将temp1赋给pre，temp1的指数域指向空，
下次循环建立temp2，pre的指数域指向temp2，然后将temp2赋给pre，temp2的指数域指向空。

创建链表的关键是要把节点连接起来，也就是要让前一个节点的指针域指向下一个节点：

显示链表：只要输入链表的头节点，就可以不断通过节点的指向来显示出所有节点的val：

void display(Node* head) {Node* temp=head->next;int e;cout << "该链表的遍历依次为：";while (temp!=NULL) {e = temp->val;cout << e << " ";temp = temp->next;}cout << "\n";
}

习题1：合并两个链表

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* preHead = new ListNode(-1);ListNode* prev = preHead;while (l1 != nullptr && l2 != nullptr) {if (l1->val < l2->val) {prev->next = l1;l1 = l1->next;} else {prev->next = l2;l2 = l2->next;}prev = prev->next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev->next = l1 == nullptr ? l2 : l1;return preHead->next;}
};

习题2：删除链表中的元素

struct Node {int data;Node* next;
};int Delete(int i) {          //删除i处的数据Node* temp;temp = Head;int j = 0;while (temp && j < i - 1) {temp = temp->next;j++;}if (!temp || j > i - 1) {cout << "删除位置错误";return -1;}else {Node* s;s = temp->next;temp->next = s->next;delete s;}
}

 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};ListNode* deleteDuplicates(ListNode* head) {ListNode* pre=head;while(pre!=NULL && pre->next!=NULL){if(pre->val == pre->next->val){pre->next = pre->next->next;}else{pre = pre->next;}}return head;}

习题3：判断两个链表是否相交

解法一：双指针法

可以理解成两个人速度一致， 走过的路程一致。那么肯定会同一个时间点到达终点。如果到达终点的最后一段路两人都走的话，那么这段路上俩人肯定是肩并肩手牵手的。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA==NULL||headB==NULL) {return NULL;}ListNode *p1=headA;ListNode *p2=headB;while(p1!=p2){p1= p1==NULL?headB:p1->next;p2= p2==NULL?headA:p2->next;}return p1;}
};

解法二：暴力法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1=headA;ListNode *p2=headB;while(p1!=p2){p1= p1==NULL?headA:p1->next;p2= p2==NULL?headB:p2->next;}return p1;}
};

解法三：哈希表法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode*> set;ListNode* hA = headA; ListNode* hB = headB;while(hA) {set.insert(hA);hA = hA->next;}while(hB) {if(set.count(hB) == 1) return hB;hB = hB->next;}return NULL;}    
};

参考：

链接: 用c++写一个链表

链接: 哔哩哔哩视频