首页 > 其他分享 >单链表的建立-带头结点/不带头结点的尾插法和头插法以及带头结点链表的逆置

单链表的建立-带头结点/不带头结点的尾插法和头插法以及带头结点链表的逆置

时间:2024-10-11 12:49:44浏览次数:8  
标签:插法 结点 带头 LNode next LinkList end NULL

王道数据结构—单链表的建立

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode,*LinkList;

//带头结点 尾插法建立单链表
LinkList List_TailInsert(LinkList& L)
{
	//初始化链表
	L = (LNode*)malloc(sizeof(LNode));

	//输入插入的数据
	int x;
	scanf("%d", &x);

	//s:一个辅助指针用于插入数据 
	//r:一个指针用于指向最后一个结点
	LNode* s, * r = L;
	while (x != 9999) {//截止循环的条件
		s = (LNode*)malloc(sizeof(LNode));//指向一个结点的空间
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

//不带头结点 尾插法建立单链表
LinkList List_TailInsert(LinkList& L)
{
	//初始化链表
	L = NULL;

	//输入插入的数
	int x;
	scanf("%d", &x);

	//s:一个辅助指针用于插入数据 
	//r:一个指针用于指向最后一个结点
	LNode* s, * r = NULL;//(注意:此时r初始化为NULL)
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		if (L == NULL)
			L = s;//更新头指针
		else
			r->next = s;
		r = s;//更新r的值,r仍指向链表尾部
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}


//对比头插法和尾插法,为什么尾插法不需要显式地写 L->next = NULL;
//隐含的初始化:
//在第一次插入节点时,r->next = s; 实际上已经将 L->next 设置为 s,这意味着 L->next 被初始化为链表的第一个实际数据节点。因此,即使没有显式地写 L->next = NULL; ,L->next 也会在第一次插入节点时被正确初始化。


//带头结点 头插法建立单链表
LinkList List_HeadInsert(LinkList& L)
{
	//初始化单链表
	L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;

	//输入插入的数据
	int x;
	scanf("%d", &x);

	//s:一个辅助指针用于插入数据
	LNode* s;
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}


//不带头结点 头插法建立单链表
LinkList List_HeadInsert(LinkList& L)
{
	//初始化单链表
	L = NULL;

	//输入插入的数据
	int x;
	scanf("%d", &x);

	//s:一个辅助指针用于插入数据
	LNode* s,*r;
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L;
		L = s;
		scanf("%d", &x);
	}
	return L;
}

//链表的逆置(反转)
//方法1:头插法
//带头结点
LinkList List_Reserve(LinkList& L)
{
	//判断链表是否为空
	if (L == NULL || L->next == NULL)
		return L;

	//p:一个辅助指针指向当前结点
	//q:一个辅助指针指向当前结点的后继结点,防止链断
	LNode* p;
	LNode* q;

	//初始化
	p = L->next;//指向第一个结点
	L->next = NULL;//断开与后面结点的联系

	//依次将结点摘下重新头插
	while (p != NULL){
		q = p->next;//暂存p的后继
		//头插
		p->next = L->next;
		L->next = p;
		p = q;//更新p结点
	}
	return L;
}

//方法二:原地逆置:不借助额外的内存空间O(1)的空间复杂度
LinkList List_Resreve(LinkList& L)
{
	//判断链表是否为空
	if (L == NULL || L->next == NULL)
		return L;

	//beg:一个辅助指针指向当前结点
	//end:一个辅助指针指向当前结点的后继结点,防止链断
	LNode* beg;
	LNode* end;

	//初始化
	beg = L->next// beg 指向链表的第一个实际数据节点
	end = L->next->next;// end 指向 beg 的后继节点

	//依次将结点原地逆置
	while (end != NULL) {
		beg->next = end->next;// 保存 end 的后继节点
		end->next = L->next;// 将 end 插入到头节点之后
		L->next = end;// 更新头节点的 next 指针
		end = beg->next; // 更新 end 指针,指向下一个待处理的节点
	}
	return L;
}

标签:插法,结点,带头,LNode,next,LinkList,end,NULL
From: https://blog.csdn.net/2301_79912259/article/details/142851247

相关文章

  • c++单链表(带头结点)
    #include<iostream>usingnamespacestd;//定义typedefstruct_LinkNode{  intdata;//结点的数据域  struct_LinkNode*next;//结点的指针域}LinkNode,Linklist;//初始化boolInitList(Linklist*&L){  L=newLinkNode;  if(!L)returnfalse; ......
  • 19. 删除链表的倒数第 N 个结点
    相当于删除正数第n个节点classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){if(!head)returnhead;intlistLength=0;ListNode*temp=head;while(temp){temp=temp->next;......
  • 红黑树|定义、左旋函数、右旋函数和对插入结点的修复
    红黑树|定义、左旋函数、右旋函数和对插入结点的修复1.红黑树类的定义2.左旋函数和右旋函数3.对插入结点的修复1.红黑树类的定义enumclassColor{ RED, BLACK};template<typenameKey,typenameValue>classRedBlackTree{ classNode { public: Key......
  • 【LeetCode Hot 100】19. 删除链表的倒数第N个结点
    题目描述由于单向链表只能从头往后遍历,所以无法向数组那样的随机存取结构一样进行下标运算,也无法从链表尾向前数n个结点。本题有两个思路,个人觉得都比较简单。可以先遍历一遍链表得到链表的长度len,然后再从头往后数len-n个结点就是所求结点。可以使用快慢指针,快指针先移动n......
  • 链表的中间结点
    链表的中间结点思路1:1.若链表为空,直接返回null2.若链表不为空,我们可以先求的链表的长度,让得到的链表长度/2,再让ListNodecur=head,cur走上链表长度/2次,就可以返回中间节点了publicintsize(ListNodehead){if(head==null){return0;......
  • 代码随想录Day4 | LeetCode 24. 两两交换链表中的节点、LeetCode 19. 删除链表的倒数
    LeetCode24.两两交换链表中的节点递归思想#Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defswapPairs(self,head:Optional[ListNode......
  • Leetcode 19.删除链表的倒数第第N个结点
    1.题目基本信息题目:给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。地址:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/2.解题方法2.1.解题思路使用快慢指针2.2.解题步骤第一步,初始化快指针为head,慢指针指向一个哑结点,哑结点......
  • Day4||24.两两交换链表中的节点|19.删除链表的倒数第n个结点|面试题:链表相交|142.环形
    24.两两交换链表中的节点题目:24.两两交换链表中的节点-力扣(LeetCode)给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。图解思路首先,虚拟头结点挺方便链表进行增删改操作的。本题操作用到三......
  • 19_删除链表的倒数第N个结点
    19_删除链表的倒数第N个结点【问题描述】给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。示例一:输入:head=[1],n=1输出:[]示例二:输入:head=[1,2],n=1输出:[1]提示:链表中结点的数目为sz1<=sz<=300<=Node.val<=1001<=n<=sz【算......
  • 876. 链表的中间结点
    题目链接876.链表的中间结点思路快慢指针-经典应用题题解链接没想明白?一个视频讲透!(Python/Java/C++/Go/JS/Rust)关键点whilefastandfast.next:...时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码实现:classSolution:defmiddleNode(self,head......