链表基本操作与题型总结_链式表基本操作题目要求是什么

1.链表的基本操作

1.1创建链表

#include<stdio.h>
#include<malloc.h>
typedef struct node
{
	int data;
	struct node *link;
}LNode,*LinkList;

LinkList create(int n) //创建链表
{
	LinkList p,r,list=NULL; //r是首元节点
	for(int i=0;i<n;i++)//n是元素个数
	{
		p=(LinkList)malloc(sizeof(LNode));//给链表分配空间
		p->data=i;//赋值元素
		p->link=NULL;
		if(list==NULL)
		{
			list=p;
		}
		else
		{
			r->link=p; //将新节点连接到链表尾部
		}
		r=p; //r始终指向末尾
	}
	return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1.2求链表的长度

一般算法
int Length(LinkList list)
{
	LinkList p=list;
	int sum=0;
	while(p!=NULL)
	{
		sum++;
		p=p->link;
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12

递归算法
int Length(LinkList list)
{
	if(list!=NULL)
	{
		return 1+Length(list->link);//要加上根节点
	}
	else
	{
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

1.3确定元素item在链表中的位置

LinkList Find(LinkList list,int item)
{
	LinkList p=list;
	while(p!=NULL && p->data!=item)
	{
		p=p->link;
	}
	return p;
}
1
2
3
4
5
6
7
8
9

1.4在非空链表第一个链接点插入信息为item的节点

//思路：创建一个新的链接点插入到链表中
void InsertLink1(LinkList &list,int item)//注意要加引用，因为要改变链表的元素
{
	LinkList p;
	p=(LinkList)malloc(sizeof(LNode));
	p->data=item;
	p->link=list;
	list=p;//list指向新的节点
}
1
2
3
4
5
6
7
8
9

1.5在非空末尾插入信息为item的链接点

void InsertLink2(LinkList list,int item)
{
	LinkList p,r;
	r=list;
	while(r->link!=NULL)
	{
		r=r->link;
	}//找到链表末尾节点的地址
	p=(LinkList)malloc(sizeof(LNode));
	p->data=item;
	p->link=NULL;
	r->link=p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.6逆转一个线性链表

//迭代法
LinkList reverse(LinkList list)
{
	if(list==NULL)
	{
		return NULL;
	}
	LinkList pre=NULL,cur=list,next;
	//三个指针分别表示前一个节点，当前节点和下一个节点
	while(cur)
	{
		next=cur->link;//保存链表该节点的下一个节点
		cur->link=pre;//变换指向
		pre=cur;
		cur=next;
	}
	return pre;//此时pre指向最后一个节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//递归法
   LinkList reverseList ( LinkList list )
    {
        if (list == NULL ||list -> link ==NULL ) 
			returnlist ;
       
        LinkList p = reverseList (list -> link ); 
		//递归之后为从后往前开始转向
       list -> link -> link =list ;
       list -> link = NULL ;
        return p ;
    }
1
2
3
4
5
6
7
8
9
10
11
12

1.7销毁链表

void Delete(LinkList &list)
{
	LinkList p=list;
	while(p!=NULL)
	{
		list=p->link;
		free(p);
		p=list;
	}
}

1
2
3
4
5
6
7
8
9
10
11

1.8将两个链表连在一起

{
	ListLink p;
	p=list1;
	while(p!=NULL)
	{
		p=p->link;
	}
	p->link=list2;
}
1
2
3
4
5
6
7
8
9

1.9复制一个链表

LinkList Copy(LinkList list)
{
	LinkList lista;
	if(list==NULL)
	{
		return NULL;
	}
	else
	{
		lista=(LinkList）malloc(sizeof(TNode));
		lista->data=list->data;
		lista->link=Copy(list->link);
	}
	return lista;
}
	 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.91将链表中数据域最大的那个链接点移动到链表末尾

//运用了双指针p,q
void Remove(LinkList &list)  
{
	LinkList p=list,q=list->link;//q是数据域最大值的节点
	LinkList r=list,s;//s是最大值的前驱节点
	while(p!=NULL)
	{
		if(p->data>q->data)
		{
			s=r;//s指向最大值节点的前驱节点
			q=p;//q指向最大值节点
		}
		r=p;
		p=p->link;//p移到下一个节点
	}
	if(q!=r)//若数据域最大的节点不是末尾
	{
		if(q==list)//若为头结点
			list=list->link;
		else
			s->link=q->link;
		    r->link=q;//r是尾节点，将尾节点下一个节点指向q,此时q是尾节点
			q->link=NULL;//将新的末尾节点的指针域为空
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2.链表的题型总结

2.1循环链表

定义：从表中任意一个链节点出发都可以访问到表的其他节点。
注意：为了解决问题方便，可以判断寻找最后一个元素，在链表的第一个链节点前面设置一个特殊节点，即头结点,头结点的数据域可以不输入信息，也可以存放链表长度等信息。

//尾插法建立单链表，并让最后一个结点的指针域指向头结点
void CreateFromTail(LinkList list)//尾插法建立单链表
{
 TNode *s, *rear;
 int i;
 rear = (TNode *)list;
 int flag = 1;
 while (flag)
 {
  scanf("%d", &i);
  if (i != -1)
  {
   s = (TNode *)malloc(sizeof(TNode));
   s->data = i;
   rear->link = s;
   rear = s;
  }
  else
  {
   flag = 0;
   
  }
 }
 rear->link = list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2.2一元多项式相加减

#include<iostream>
using namespace std;
typedef struct Node
{
	int coef;//系数
	int exp;//项数
	struct Node *link;
}TNode,* LinkList;

LinkList create(int coef,int exp)//创建链表
{
	 LinkList p,r,list=NULL;
	 p=(LinkList)malloc(sizeof(TNode));
	 p->coef=coef;
	 p->exp=exp;
	 p->link=NULL;
	 if(list==NULL)
		 list=p;//list为头结点
	 else
	 { 
		 r->link=p;//r始终指向链表末尾
	 }
	 r=p;
	 return (list);
}

//添加节点
LinkList Add(LinkList list,int ep,int cof)
{
	LinkList w;
	w=(LinkList)malloc(sizeof(TNode));
	w->coef=cof;
	w->exp=ep;
	list->link=w;
	return w;//返回当前链表节点最后的位置
}

//多项式加法
LinkList Padd(LinkList list1,LinkList list2)
{
	LinkList c;//存放相加后的元素
	LinkList r,p=list1,q=list2;
	int x;
	c=(LinkList)malloc(sizeof(TNode));
	r=c;//r总是指向链表c的末尾节点
	while(p!=NULL && q!=NULL)
	{
		if(p->exp==q->exp)//项数相同则相加
		{
			x=p->coef+q->coef;//对应的系数相加
			if(x!=0)//若相加的结果不为零
			{
				r=Add(r,p->exp,x);//将新产生的一项加入多项式
				q=q->link;
				p=p->link;
			}
		}
		if(p->exp<q->exp)
		{
			r=Add(r,q->exp,q->coef);
			q=q->link;
		}
		else
		{
			r=Add(r,p->exp,p->coef);
			p=p->link;
		}
	}
	while(p!=NULL)//将p剩余的项数相加
	{
		r=Add(r,p->exp,p->coef);
		p=p->link;
	}
	while(q!=NULL)//将q剩余的项数相加
	{
		r=Add(r,q->exp,q->coef);
		q=q->link;
	}
	r->link=NULL;//此时r指向最后一个元素所以它后面的指针为元素
	c=c->link;//此时c指向链表的第一项
	free(p);
	return c;
}


//多项式减法
LinkList Psub(LinkList list1,LinkList list2)
{
	LinkList c;//存放相减后的元素
	LinkList r,p=list1,q=list2;
	int x;
	c=(LinkList)malloc(sizeof(TNode));
	r=c;//r总是指向链表c的末尾节点
	while(p!=NULL && q!=NULL)
	{
		if(p->exp==q->exp)
		{
			x=p->coef-q->coef;
			if(x!=0)
			{
				r=Add(r,p->exp,x);//将新产生的一项加入多项式
				q=q->link;
				p=p->link;
			}
		}
		if(p->exp<q->exp)
		{
			r=Add(r,q->exp,q->coef);
			q=q->link;
		}
		else
		{
			r=Add(r,p->exp,p->coef);
			p=p->link;
		}
	}
	while(p!=NULL)
	{
		r=Add(r,p->exp,p->coef);
		p=p->link;
	}
	while(q!=NULL)
	{
		r=Add(r,q->exp,q->coef);
		q=q->link;
	}
	r->link=NULL;//此时r指向最后一个元素所以它后面的指针为元素
	c=c->link;//此时c指向链表的第一项
	free(p);
	return c;
}


void Print(LinkList list)
{
	LinkList p=list;
	while(p!=NULL)
	{
		cout<<p->coef<<"x^"<<p->exp<<"+";
		p=p->link;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

2.3从尾到头打印链表

//法一：利用栈的先进后出

struct Node 
{
    int data;
    struct ListNode *next;
    ListNode(int x) :
      data(x), next(NULL) {
        }
  }ListNode,*ListLink;
vector<int> Print_List(ListLink list)
{
	stack<ListLink> node;
	ListLink p=list;
	while(p!=NULL)
	{
		node.push(p);//将链表节点入栈
		p=p->next;
	}
	vector<int> result;//存储结果
	while(!node.empty())
	{
		p=node.top();
		result.push_back(p->data);
		node.pop();
	}
	return result;
}

//法二：将链表反转
 LinkList reverse(LinkList list)
{
	if(list==NULL)
	{
		return NULL;
	}
	LinkList pre=NULL,cur=list,next;
	//三个指针分别表示前一个节点，当前节点和下一个节点
	while(cur)
	{
		next=cur->link;//保存链表该节点的下一个节点
		cur->link=pre;//变换指向
		pre=cur;
		cur=next;
	}
	return pre;//此时pre指向最后一个节点
}
 void Print_List(LinkList list)
 {
	 LinkList p=list;
	 while(p!=NULL)
	 {
		 cout<<p->data<<" ";
		 p=p->link;
	 }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

2.4合并两个有序的链表

Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

LinkList Merge_Two_Lists ( LinkList list1 , LinkList list2 )
    {
        if ( list1 == NULL ) 
           return list2 ;
        if ( list2 == NULL ) 
           return list1 ;
       
        ListNode prehead ( 0 ); //头结点前面附加一结点（ 当原链表头结点可能会变化时都可以考虑使用prehead ）
        LinkList p = & prehead ; //新链表结点指针
        for (; list1 != nullptr && list2 != nullptr ; p = p->next ) //比较list1和list2各结点大小，归并
        {
            if ( list1 -> data < list2 -> data )
            {
                p ->next = list1 ; //下一个结点指向list1结点
                list1 = list1->next;
            }
            else
            {
                p -> next = list2 ;
                list2 = list2 -> next ;
            }
        }
       
        if ( list1 != nullptr ) 
			p->next = list1 ; //处理剩余结点
        if ( list2 != nullptr ) 
			p -> next = list2 ;
        return prehead.next; //返回头结点指针
    }
    //拓展：合并两个有序的数组也是类似思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.5Add Two Numbers

题目描述：
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

思路：首先要想到用一个标志位来保存进位，依次将两个链表对应的位置的元素相加，另外要注意判断两个链表是否已经到达结尾。

LinkList AddTwoNumbers(LinkList a1,LinkList a2)
{
	ListNode preHead(0);
	LinkList p=&preHead;//头结点,用于保存首结点指针，以及初始化p,p是新的链表，存储相加后的数据
    int flag = 0 ; //进位
	while(a1 || a2 || flag)
	{
		int sum=(a1?a1->data :0)+(a2?a2->data :0)+flag;
		//对应位相加，判断是否为空，若空则加0
		flag=sum/10;//保存进位
		p->next=(LinkList)malloc(sizeof(ListNode));
		p->data=sum%10;
		//创建新的节点，并赋值
		p=p->next;
		a1 = a1 ? a1 -> next : a1 ; //若为空，则仍为空，若不为空，指向下一个结点
        a2 = a2 ? a2 -> next : a2 ; 
     }
        return preHead.next ; //返回首结点指针
       
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.6Odd Even Linked List

题目描述：将链表中所有奇数序号节点放到前面，偶数节点放到后面
Example 1:
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:
Input: 2 ->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
思路：此题与数组的将奇数放到前面，偶数放到后面类似，但数组放的是值，链表放的是节点。此题设置两个链表，一个存储奇数序号一个存储偶数序号，再将两个链表连在一起。

LinkList Odd_NumberEven_Number ( LinkList list )
{
        if (! list ) 
			return list ;
        LinkList Odd_Number = list ; 
		// 奇数序列结点指针与头指针
        LinkList Even_Number = list -> next ,even = Even_Number ;
		// 偶数序列结点指针与头指针
        while ( even && even->next ) 
		// 偶数序列指针判断 ( 循环时一般用后面的指针来判断是否结束循环) 对于走两步的指针p均需要判断p与p->next是否为空
        {
            Odd_Number -> next = Odd_Number -> next -> next ; 
			// 连接奇数序列结点 , 每次走两步 ，先连接前面的指针
            even -> next = even -> next -> next ; 
			// 连接偶数序列结点
           
            Odd_Number = Odd_Number -> next ; 
			// 指向下一个奇结点
            even = even -> next ;
        }
        Odd_Number -> next = Even_Number ; 
		// 连接奇序列链表和偶序列链表
        return list ;
       
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.7链表中的倒数第k个节点

题目描述：输入一个链表，输出该链表的倒数第K个节点，
加入一个链表有6个节点，分别是1,2,3,4,5,6.这个链表的倒数第3个数是值为4的节点。

一般思路：假设链表有n个节点，那么倒数第k个节点就是从头往后走n-k+1步就可以了，那么如何得到n呢，只需从头开始遍历链表，每经过一个节点计数器+1就可以了，也就是说要遍历两次，复杂度为O(n^2)。

优化思路：双指针法，第一个指针从头开始走k-1步，第二个指针保持不动，从第k步开始，第二个指针也开始从头指针开始遍历，当第一个指针走到末尾时，第二个指针刚好是第k个节点。

ListLink FindkthtoTail(ListLink head,int k)
{
	if(head==NULL || k==0)
		return NULL;
	ListLink phead=head;
	ListLink pbehind=NULL;
	for(int i=0;i<k-1;i++)//第一个指针先走k-1步
	{
		phead=phead->next;
	}
	pbehind=head;
	while(phead->next!=NULL)
	{
		phead=phead->next;
		pbehind=pbehind->next;
	}
	return pbehind;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

举一反三：当我们用一个指针遍历不能解决问题的时候可以尝试用两个指针来遍历链表，可以让其中一个指针的速度更快一些，比如一次在链表中走两步或者先在链表中走若干步。