# 单链表

单链表的结构示意图

  单链表是一种顺序存储的结构. 有一个头结点,没有数据,只存储链表第一个节点的地址. 除了尾结点,每个节点都有唯一的直接后继. 所以,单链表中查询第i个元素必须知道头结点且顺序访问前i-1个结点数据才能找到.

# 单链表统一结构

typedef int ElementType;
typedef struct Node{
     ElementType data;
     struct Node* next;
}*ListNode;

# 查找单链表中倒数第 k 个结点

ListNode* findKth(ListNode* head, int k){
	if(head == NULL || k == 0)  //倒数第0个无意义
		return NULL;

	ListNode* p = head;
	ListNode* q = head;
	for(int i = 0;i < k - 1; i++){ //先让第一个指针走到第k个结点,如果链表不够长,直接返回空
		if(p->next != NULL)
		    p = p->next;
		else
		    return NULL;
	}

	while(p->next != NULL){  //p只要走到结尾,q即为倒数第k个结点
	    p = p->next;
	    q = q->next;
	}

	return p;
}

# 合并两个有序的单链表,合并后依然有序

ListNode* Merge(ListNode* p, ListNode* q){	//采用归并的思想
	if(!p) return q;
	if(!q) return p;		//若有一个为空,返回另一个

	ListNode *r = NULL;
	ListNode *rhead = NULL;
	if(p->data < q->data){    //定下头指针
		rhead = p;
		p = p->next;
	}
	else{
		rhead = q;
		q = q->next;
	}
	r = rhead;   //r当工作指针
	while(p!=NULL && q!=NULL){	//公共部分进行有序合并
		if(p->data < q->data){
			r->next = p;
			p = p->next;
		else{
			r->next = q;
			q = q->next;
		}
	r = r->next;
	}

	if(p == NULL) r->next = q;	//公共部分跳出后,若有剩下,则直接指向剩下的头
	if(q == NULL) r->next = p;

	return rhead;
}

# 单链表的就地逆置(头插法)

ListNode* reverseList(ListNode* p){
	ListNode* q = p;
	ListNode* qpre = NULL;
	while(q != NULL){
		ListNode *r = q->next; 		//防止断链
		q->next = qpre;		//保存尾指针
		qpre = q;         //完成一次翻转,前移
		q = r;
	}
	return qpre;
}

# 从尾到头打印单链表

const int maxn = 1010;    	//数组无法变长,尽量设一个最大值可以容下链表结点数
void reversePrint(ListNode *head){ 	//原文用cpp且返回变长数组,此处仅仅只是打印,且没用std
	if(head === NULL)
		return;		//日常判空
	int print[maxn];
	int top = -1;
	while(top != -1 || head != NULL){
		print[++top] = head->data;
		head = head->next;
	}
	while(top>=0){
		printf("%d",print[top--]);
		if(top>0)
			printf(" ");
	}
}

# 带环的单链表中,找到环的起始点

ListNode* meetingNode(ListNode *p){	//判断是否有环,快慢指针的方法
	if(p == NULL || p->next == NULL)
		return NULL;
	ListNode *slow = p, *fast = p;
	while(fast->next != NULL && fast->next->next !=NULL){  //一快一慢,有环必定相遇
		slow = slow->next;
		fast = fast->next->next;
		if(fast == slow)
			return fast;
	}
	return NULL;
}

ListNode* entryNode(ListNode *p){     //找到环的入口结点
	ListNode *meeting = meetingNode(p);
	if(meeting == NULL) return NULL; //无环或者空链表
	int loopNodes = 1;
	ListNOde *node = meeting;
	while(node->next != meeting){
		node = node->next;
		loopNodes++;		//计算环的长度
	}

	ListNode *head = p;
	for(int i=0;i<loopNodes;i++)
		head = head->next;

	ListNode *another = p;
	while(head != another){
		head = head->next;
		another = another->next;
	}

	return head;
}

# 判断两个单链表相交的第一个交点

//由于有重复操作,封装一些重复的方法还是有必要的
int getLength(ListNode *p){  //获取链表长度
	int num = 0;
	while(p!=NULL){
		p=p->next;
		num++;
	}
	return num;
}

ListNode* longMustWalk(ListNode *p,int k){	//长链必须先移到和短链一样长度的起点处
	ListNode *q = p;
	while(k>=0){
		q = q->next;
	}
	return q;
}

ListNode* findfirstCommom(ListNode* p, ListNode* q){  //找到第一个交点
	int lenp = getLength(p);
	int lenq = getLength(q);
	if(lenp>lenq) p = longMustWalk(p,len1-len2);
	else q = longMustWalk(q,len2-len1);	//让长的那一条,先走掉长-短的结点数
	while(p!=NULL && q!=NULL && p!=q){
		p = p->next;
		q = q->next;
	}

	return p;
}

# 删除链表中重复的结点

ListNode* delduplication(ListNode* p){		//重复的全部删掉,不保留
	if(p == NULL || p->next == NULL)
		return p;
	ListNode* q = (ListNode*)malloc(sizeof(struct Node));
	q->data = -1;
	q->next = p;		//此处为若头结点被删除的处理
	ListNode *pre = q, *r = p, *next = NULL;
				//对应前驱,工作指针,next指针
	while(r!=NULL && r->next != NULL){
		next = r->next;
		if(r->val == next->val){
			while(next != NULL && r->val == next->val)
				next = next->next;
			pre->next = next;
			r = next;
		}
		else{
			pre = r;
			r = next;
		}
	}
	return q->next;			//返回的是有带头结点的
}

  阅读原文