本篇主要记载链表的一些基本算法和问题。

链表的长度

这个算法的思想简单，这里就不做过多解释，直接给出非递归和递归的代码
非递归算法： 

1
2
3
4
5
6
7
8
9
10
11
12
13
int GetListLength(ListNode* list)
{
	ListNode* tmp=list;
	int len=0;
	if(tmp==NULL)
		return len;
	while(tmp!=NULL)
	{
		len++;
		tmp=tmp->next;
	}
	return len;
}

递归算法： 

1
2
3
4
5
6
7
8
9
10
int RecuGetListLength(ListNode* list)
{
	ListNode* tmp=list;
	if(tmp==NULL)
		return 0;
	else{
		tmp=tmp->next;
		return RecuGetListLength(tmp)+1;
	}
}

翻转单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode* ReverseList(ListNode* list)
{
	if(list==NULL || list->next==NULL)
		return list;
	//l1,l2,l3 分别依次指向原链表的三个节点
	ListNode* l1=list;
	ListNode* l2=list->next;
	ListNode* l3;
	while(l2!=NULL)
	{
		//翻转相邻的两个节点
		l3=l2->next;
		l2->next=l1;
		//更新节点的位置
		l1=l2;
		l2=l3;
	}
	//将原链表的头指针置为NULL
	list->next=l2;
	//更新新链表的头节点
	list=l1;
	return list;
}

查找倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* RecipKthNode(ListNode* list,int k)
{
	/*基本思路，让第一个指针先走k步，接着第二个指针跟着走，直到第一个指针走到最后
	，这时第二个指针就走到倒数第K个位置*/
	ListNode* tmp=list;
	//考虑到链表的长度小于k，先置为NULL
	ListNode* kthnode=NULL;
	int count=0;
	while(tmp!=NULL)
	{
		count++;
		if(kthnode!=NULL)
			kthnode=kthnode->next;
		if(count==k)
		{
			kthnode=list;
		}
		tmp=tmp->next;
	}
	return kthnode;
}

从尾到头打印链表

这个问题你要是想到递归，那就没什么问题了,不过还是那就话，递归不好理解。 

1
2
3
4
5
6
7
8
void print_begin_tail(ListNode* list)
{
	if(list!=NULL)
	{
		print_begin_tail(list->next);
		cout<<list->value<<endl;
	}
}

判断链表是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool HasCircle(ListNode* list)
{
	/*思路就是一个快指针，每次走两步，一个慢指针，每次走一步，如果
	快指针追上慢指针，则说明有环存在，否则没有环*/
	ListNode* fast=list;
	ListNode* slow=list;
	while(fast!=NULL&& fast->next!=NULL)
	{
		fast=fast->next->next;
		slow=slow->next;
		if(fast==slow)
			return true;
	}
	retrun false;
}

删除节点

这里要求O（1）的时间复杂度。 

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
void Delete(ListNode* phead,ListNode* tobedelete)
 {
 	if(tobedelete == NULL || phead == NULL)
 		return;
 	ListNode* temp = phead;
 	//将下一个节点的数据复制到本节点，然后删除下一个节点
	if(tobedelete->next != NULL)
	{
		tobedelete->value = tobedelete->next->value;
		ListNode* temp = tobedelete->next;
		tobedelete->next = tobedelete->next->next;
		delete temp; 
	}
	else //要删除的是最后一个节点
	{
		if(phead == tobedelete)//链表中只有一个节点的情况
		{
			phead = NULL;
			delete tobedelete;
		}
		else
		{
			ListNode* pnode = phead;
			while(pnode->next != tobedelete)//找到倒数第二个节点
				pnode =pnode->next;
			pnode->next = NULL;
			delete tobedelete;
		}
	}
 }