1、从头到尾打印链表
首先创建单链表,定义一个尾插入和删除操作：
struct Listnode { int m_nKey; Listnode *next; }; void init_List(Listnode **head) { *head=new Listnode; if(*head==NULL) return; (*head)->next=NULL; (*head)->m_nKey=0; } void add_node(Listnode** head,int val) { Listnode* node=new Listnode; if(node==NULL) return; node->m_nKey=val; node->next=NULL; if((*head)->next==NULL) (*head)->next=node; else { Listnode* temp=(*head)->next; while(temp->next!=NULL) temp=temp->next; temp->next=node; } } void delete_node(Listnode** head,int val) { Listnode* temp=(*head)->next; Listnode* before_temp=*head; if((*head)->next==NULL) return; else { while(temp->m_nKey!=val&&temp->next!=NULL) { before_temp=temp; temp=temp->next; } if(temp!=NULL&&temp->m_nKey==val) { before_temp->next=temp->next; delete(temp); } } }
两种方法可以实现从尾到头打印，一种是栈，另一种是递归：
vector<int> rprint1(Listnode* head) //栈实现 { vector<int> print_data; stack<Listnode*> s_node; Listnode* node=head; while(node!=NULL) { s_node.push(node); node=node->next; } while(!s_node.empty()) { print_data.push_back(s_node.top()->m_nKey); s_node.pop(); } return print_data; } void rprint2(Listnode* head) //递归实现 { if(head!=NULL) { if(head->next!=NULL) rprint2(head->next); cout<<head->m_nKey<<" "; } }
二、删除从栈尾部开始算的第n个节点
可是使用双指针控制距离，实现定位
void delete_r_n_node(Listnode *head,int n) //n指从尾部开始数的位数加1 { Listnode* r1=head; Listnode* r2=head; Listnode* temp; while(n) { if(r1->next!=NULL) r1=r1->next; else return; n--; } while(r1->next!=NULL) { temp=r2; r1=r1->next; r2=r2->next; } if(r2->next!=NULL) { temp->next=r2->next; delete r2; } }
三、在O(1)时间内删除链表结点
void DeleteNode(Listnode **head,Listnode* Pdeleted) { if(*head==NULL) return; //当删除结点不是尾结点 if(Pdeleted->next!=NULL) { Listnode* temp=Pdeleted->next; Pdeleted->m_nKey=Pdeleted->next->m_nKey; Pdeleted->next=Pdeleted->next->next; delete temp; temp=NULL; } //当删除节点是尾结点 else if((*head)->next==Pdeleted) { delete Pdeleted; Pdeleted=NULL; (*head)->next=NULL; } else { Listnode* temp=*head; while(temp->next!=Pdeleted) temp=temp->next; if(temp->next==Pdeleted) { temp->next=NULL; delete Pdeleted; Pdeleted=NULL; } } }
四、反转链表
Listnode* ReverseList1(Listnode* head) { Listnode* rev=NULL; //头结点为空 if(head==NULL) return NULL; Listnode* temp=head; Listnode* pPrew=NULL; while(temp!=NULL) { Listnode* pnext=temp->next; if(pnext==NULL) rev=temp; temp->next=pPrew; pPrew=temp; temp=pnext; } return rev; } Listnode* ReverseList2(Listnode* head) { if(head==NULL||head->next==NULL) return head; else { Listnode* newlist=ReverseList2(head->next); head->next->next=head; head->next=NULL; return newlist; } }
五、合并两个排好序的链表
//递归实现 Listnode* mergeList1(Listnode* L1,Listnode* L2) { //当存在空指针时 if(L1==NULL) return L2; else if(L2==NULL) return L1; Listnode *merge_node=NULL; if(L1->m_nKey>=L2->m_nKey) { merge_node=L2; merge_node->next=mergeList1(L1,L2->next); } else { merge_node=L1; merge_node->next=mergeList1(L1->next,L2); } return merge_node; } //迭代循环实现 Listnode* mergeList2(Listnode* L1,Listnode* L2) { if(L1==NULL) return L2; else if(L2==NULL) return L1; Listnode* merge_node=NULL; Listnode* node=NULL; if(L1->m_nKey<=L2->m_nKey) { node=L1; L1=L1->next; } else { node->next=L2; L2=L2->next; } merge_node=node; //获取头指针 while(L1!=NULL&&L2!=NULL) { if(L1->m_nKey<=L2->m_nKey) { node->next=L1; node=L1; L1=L1->next; } else { node->next=L2; node=L2; L2=L2->next; } } if(L1!=NULL) node->next=L1; else node->next=L2; return merge_node; }
六、寻找两个链表的第一个公共结点
Listnode* FindFirstCommonNode(Listnode* L1,Listnode* L2) { int L1_length=getlengthlist(L1); int L2_length=getlengthlist(L2); Listnode* long_list=NULL; Listnode* short_list=NULL; if(L1_length&&L2_length) return NULL; int i=0; if(L1_length>=L2_length) { long_list=L1; short_list=L2; i=L1_length-L2_length; } else { long_list=L2; short_list=L1; i=L2_length-L1_length; } while(i) { i--; long_list=long_list->next; } while(long_list&&short_list&&(long_list==short_list)) { long_list=long_list->next; short_list=short_list->next; } if(long_list==short_list) return long_list; else return NULL; }