链表的常见操作

By MLTech at: 2016-12-05

链表的常见操作，摘自《剑指offer》。

0 链表的增加和删除操作。
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
//LinkedList
struct  ListNode
{
	int m_nValue;
	ListNode* m_pNext;
};

void AddToTail(ListNode** pHead, int value)
{
	ListNode* pNew=new ListNode();
	pNew->m_nValue=value;
	pNew->m_pNext=NULL;

	if(*pHead == NULL)
		*pHead=pNew;
	else
	{
		ListNode* p= *pHead;
		while(p=m_pNext != NULL)
		{
			p=p->m_pNext;
		}
		p->m_pNext=pNew;
	}
}

void RemoveNode(ListNode** pHead, int value)
{
	if(pHead == NULL || *pHead == NULL)
		return;

	ListNode* pToDeleted=NULL;
	if((*pHead)->m_nValue == value)
	{
		pToDeleted=*pHead;
		*pHead=(*pHead)->m_pNext;
	}else
	{
		ListNode* p=*pHead;
		while(p->m_pNext != NULL && p->m_pNext->value!=NULL)
			p=p->m_pNext;

		if(p->m_pNext != NULL && p->m_pNext->value == value)
		{
			pToDeleted = p->m_pNext;
			p->m_pNext=->m_pNext->m_pNext;
		}
	}

	if(pToDeleted != NULL)
	{
		delete pToDeleted;
		pToDeleted = NULL;
	}
}
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
// 从尾到头打印链表  迭代
void PrintListReversingly_Itetatively(ListNode* pHead)
{
	std::stack<ListNode*> nodes;
	ListNode* p=pHead;
	while(p!=NULL)
	{
		nodes.push(p);
		p=p->m_pNext;
	}

	while(!nodes.empty())
	{
		p=node.top();
		printf("%d \n", p->m_nValue);
		nodes.pop();
	}
}

// 从尾到头打印链表  递归
void PrintListReversingly_Recursively(ListNode* pHead)
{
	if(pHead!=NULL)
	{
		if(pHead->m_pNext!=NULL)
			PrintListReversingly_Recursively(pHead->m_pNext);
		printf("%d \n", pHead->m_nValue);
	}
}