链表总结

单链表

结构体表示：

typedef struct node{int data;struct node *next;
}*list;

1、不带头结点的单链表，递归删除所有结点值为x的链表

注意必须加引用，不加引用会断链

void deletenode(list &head, int x){			//必须加引用 struct node *p;if(head == NULL) return;else if(head->data == x){p = head;head = head->next;					//这里不会断链 head->next = head->next->nextfree(p);deletenode(head, x); }else{deletenode(head->next, x);}
} 

2、链表的排序（默认带头结点）

（1）直接插入排序

思路：

• 需要三个指针
  • 一个工作指针p
  • 一个指针nextp 保存p的next指针用于后序遍历
  • 一个遍历指针q 找到插入位置，每次找的时候，指向head，比较head->next

代码：

void  InsertSort_Node(list &head){struct node *p = head->next,*nextp, *q;head->next = NULL;while(p!=NULL){nextp = p->next;q = head;while(q->next!=NULL && q->next->data < p->data){//找到插入位置 q = q->next;}p->next = q->next;								//插入 q->next = p;p = nextp;}
}

（2）冒泡排序

思路：

• 设置四个指针
  • q指针用来每一层的遍历
  • pre指针，指向q的前一个节点方便指针的交换
  • q指针，用来比较
  • tail指针，指向未排好序的最后一个节点
• 实现方式：
  • 模拟冒泡排序，每次pre和p都重新指向头结点，以及下一个节点
  • q取p的下一个节点，遍历链表，当出现前一个数大于后一个数时交换指针，注意交换完之后，重新交换一下q与p指针，然后再整体右移
  • 注意结束后，要更新tail指针，双重for循环也是与tail指针比较的

代码：

void BubbleSort_Node(list &head){struct	node *pre=head,*p=head->next, *q;	//三个工作节点，pre保存p的前驱节点，q指向下一个节点 struct node *tail=NULL,*temp;						//尾指针，每次冒泡前移 while(p!=tail){q = p->next;while(q!=tail){if(p->data > q->data){				//降序排序 pre->next = q;p->next = q->next;	q->next = p; //交换完之后p变成q,q变成p,整体往前走，下次交换就会出现混乱，所以p，q还要指向原来的位置才能整体往前走temp = p;p = q;q = temp;}pre = pre->next;					//pre,p,q整体往前走一步（交不交换都要往前走）p = p->next;q = q->next;}tail = p;								//tail前移 pre = head;								//重新从头开始比较 p = head->next;}
}

(3)二路归并排序 时间复杂度NlogN 在链表排序中属于较好的一种排序方式

思路：

1. 利用快慢指针找到中点，将链表分为左右两个链表
2. 递归找到左右链表的中点
3. 当递归中只剩下一个节点时，合并链表节点

代码：

list Merge_Node(list head1, list head2){			//合并两个有序链表 list newhead = (list)malloc(sizeof(struct node));list p = newhead;								//工作指针 while(head1 != NULL && head2 !=NULL){if(head1->data > head2->data){p->next = head2;head2 = head2->next;}else{p->next = head1;head1 = head1->next;}p = p->next;} if(head1!=NULL) p->next = head1;if(head2!=NULL) p->next = head2;return newhead->next; 
} list TwoRoadMergeSort_Node(list head){if(head == NULL || head->next == NULL) return head;list fast = head;list slow = head;while(fast->next != NULL && fast->next->next != NULL){fast = fast->next->next;slow = slow->next;} list mid = slow->next;							//找到中点 slow->next = NULL;list left =  TwoRoadMergeSort_Node(head);		//递归找中点 list right = TwoRoadMergeSort_Node(mid);return Merge_Node(left, right);					//归并 
} 

3、给两个单链表，找到公共节点

思路：

• 找到长链表与短链表，长的链表先把长的走完，然后一起走，遇到相同的节点就返回，否则继续走

代码：

int Length_Node(list head){//不带头结点 	求链表长度int num = 0;list p = head;while(p!=NULL){num++;p = p->next;} return num;
} list FindSameNode(list head1, list head2){int len1 = Length_Node(head1);int len2 = Length_Node(head2);list longlist, shortlist;int dist;if(len1>len2){					//找到长的链表与短的链表 dist = len1 - len2;longlist = head1;shortlist = head2;}else{dist = len2 - len1;longlist = head2;shortlist = head1;}while(dist){					//长的链表先走完更长的那部分 longlist = longlist->next;dist--; }while(longlist != NULL){		//找公共节点 if(longlist == shortlist){return longlist;}else{longlist = longlist->next;shortlist = shortlist->next; }}return NULL;					//未找到 
} 

4、将一个链表带头结点的链表分解为两个链表，一个含有奇数序列 ，一个含有偶数序列

思路：

• 创建一个节点head2，用来当第二个链表的头结点
• p指针指向所给链表head1的next，然后将head1->next置为空，方便后序插入
• 遍历p节点
• 添加计数器num
  • 如果是奇数就将p节点添加到head1的工作指针p1中
  • 如果是偶数就将p节点添加到head2的工作指针p2中

代码：

list DivlistToTwo(list &head1){list p = head1->next,q,p1,p2;	//p1,p2为head1，head2工作指针 list head2 = (list)malloc(sizeof(struct node));head1->next = NULL;p1 = head1;						//工作指针指向对应头结点 p2 = head2;	int num = 1;					//添加计数器 while(p!=NULL){					//遍历p节点 if(num%2==1){				//奇数节点 p1->next = p;p1 = p1->next;}else{						//偶数节点 p2->next = p;p2 = p2->next;}num++;						//继续遍历 p = p->next;}if(p1) p1->next =NULL;			//尾部置空 if(p2) p2->next =NULL;return head2;					//返回另外一个节点 
}