反转一个链表
struct list_node* resverse_list(struct list_node* head){ struct list_node* current = head; struct list_node* prev = NULL; while(current){ struct list_node* node = current->next; 指向第二个节点 current->next = prev; 第一个节点指向NULL prev = current; 前继节点后移 current = node; 当前节点后移 } }
单向链表如何找到倒数n个节点
---->用两个指针 ，第一个先走n步,然后两个指针同时走,当第一个指针走到尾时,返回第二个指针
struct list_node* GetLastNnode(struct list_node* head , int n){ struct list_node* pfirst = head; struct list_node* psecond = head; int count; for(count = 0 ; count < n ; count++){ if(pfirst == NULL) break; pfirst = pfirst->next; } if( n != count) // 长度不够n return NULL; while(pfirst != NULL){ psecond = psecond->next; pfirst = pfirst->next; } return psecond; }
判断链表是否有环？
----->快慢指针
bool isLoopList(struct list_node* head){ struct list_node* pfast = head; struct list_node* pslow = head; while(pfast != NULL && pfast->next != NULL){ pfast = pfast->next->next; pslow = pslow->next; if(pfast == pslow) return true; } return false; }
判断两个链表是否交叉
struct list_node* FindCrossNode(struct list_node* list1 , struct list_node* list2){ if(list1 == NULL || list2 == NULL) return NULL; struct list_node* p1 = list1; struct list_node* p2 = list2; int len1 = 0; int len2 = 0; while(p1){ p1 = p1->next; len1++; } while(p2){ p2 = p2->next; len2++; } len = len1 > len2 ? len1-len2 : len2-len1; struct list_node* long = len1 > len2 ? list1 : list2; struct list_node* short = len1 < len2 ? list1 : list2; for(int i = 0 ; i < len ; i++){ long = long->next; } while(short != NULL && long != NULL && short != long){ short = short->next; long = long->next; } return short; }
