单链表（Single Linked List）

1 理论

1、链表
链表是一种基本数据结构，其中的各对象按线性顺序排列，线性顺序由各个对象里的指针决定。它为动态集合提供了一种简单而灵活的表示方法。
链表的多种形式：

• 可以是单链接的或双链接的；
• 可以是已排序的或未排序的；
• 可以是循环的或非循环的；

2、下文中所提到的链表均指 单链表

3、单链表

• 每个元素都是一个对象，每一个对象有一个关键字 val 和一个指针 next（对象中还可以有其它的辅助数据 / 卫星数据）；
• x 为链表的一个元素，x.next 指向它的后继元素；如果 x.next = NIL，则元素 x 没有后继元素，是链表的最后一个元素（即链表的尾 / tail）；
• 属性 L.head 指向链表的第一个元素，如果 L.head = NIL ，则链表为空。

struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x),next(NULL) {}
};

struct SingleList {
	ListNode* head;
	SingleList() : head(NULL) {}
};

2 Interesting Problems

2.1 链表反转（LeetCode 206. Reverse Linked List）

#include <iostream>
using namespace std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x),next(NULL) {}
};

ListNode* reverseSingleList(ListNode* head) {
	ListNode* pre = NULL;
	while (head)
	{
		ListNode* temp = head->next;
		head->next = pre;
		pre = head;
		head = temp;
	}
	return pre;
}

int main()
{
	ListNode* headB0 = new ListNode(5);
	ListNode* headB1 = new ListNode(0);
	ListNode* headB2 = new ListNode(1);
	ListNode* headAB1 = new ListNode(8);
	ListNode* headAB2 = new ListNode(4);
	ListNode* headAB3 = new ListNode(5);	
	headB0->next = headB1;
	headB1->next = headB2;
	headB2->next = headAB1;
	headAB1->next = headAB2;
	headAB2->next = headAB3;

	ListNode* rHead = reverseSingleList(headB0);
	headB0 = rHead;
	while (headB0)
	{
		cout << headB0->val << endl;
		headB0 = headB0->next;
	}
	system("pause");
    return 0;
}
//输出
5
4
8
1
0
5

2.2 判断链表中是否存在环（LeetCode 141. Linked List Cycle）

#include <iostream>
#include <unordered_set>
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

//bool hasCycle(ListNode *head) {
//	bool result = false;
//	std::unordered_set<ListNode*> set;
//	while (head != NULL)
//	{
//		if (set.find(head) != set.end())
//		{
//			result = true;
//			break;
//		}
//		set.insert(head);
//		head = head->next;
//	}
//	return result;
//}

//大佬思维
bool hasCycle(ListNode *head) {
	bool result = true;
	if (head != NULL)
	{
		ListNode* slow = head;
		ListNode* fast = head->next;
		while (slow != fast)
		{
			if (fast == NULL || fast->next == NULL)
			{
				result = false;
				break;
			}
			slow = slow->next;
			fast = fast->next->next;
		}
	}
	else
	{
		result = false;
	}
	return result;
}

int main()
{
	ListNode* listNode1 = new ListNode(1);
	ListNode* listNode2 = new ListNode(2);
	ListNode* listNode3 = new ListNode(3);
	ListNode* listNode4 = new ListNode(4);
	ListNode* listNode5 = new ListNode(5);
	listNode1->next = listNode2;
	listNode2->next = listNode3;
	listNode3->next = listNode4;
	listNode4->next = listNode5;
	listNode5->next = listNode2;
	bool result = hasCycle(listNode5);
	std::cout << result << std::endl;
	std::system("pause");
    return 0;
}

//输出
1

2.3 链表交集（LeetCode 160. Intersection of Two Linked Lists）

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

begin to intersect at node c1.

#include <iostream>
using namespace std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x),next(NULL) {}
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
	ListNode* pa = headA;
	ListNode* pb = headB;
	while (pa != pb)
	{
		pa = pa ? pa->next : headB;
		pb = pb ? pb->next : headA;
	}
	return pa;
}

int main()
{
	ListNode* headA0 = new ListNode(4);
	ListNode* headA1 = new ListNode(1);
	ListNode* headB0 = new ListNode(5);
	ListNode* headB1 = new ListNode(0);
	ListNode* headB2 = new ListNode(1);
	ListNode* headAB1 = new ListNode(8);
	ListNode* headAB2 = new ListNode(4);
	ListNode* headAB3 = new ListNode(5);
	
	headB0->next = headB1;
	headB1->next = headB2;
	headB2->next = headAB1;
	headAB1->next = headAB2;
	headAB2->next = headAB3;
	headA0->next = headA1;
	headA1->next = headAB1;

	ListNode* res = getIntersectionNode(headA0, headB0);
	cout << res->val << endl;
	system("pause");
    return 0;
}
//输出
8