1.移除单链表中与给数相同的元素
解题思路：
初始化一个新链表，从头结点开始遍历，若相同，保存下一节点位置，再free 掉该节点，若不同将节点赋值给新链表。
代码段：
struct ListNode* removeElements(struct ListNode* head, int val) { if(head == NULL) return NULL; struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur) { //如果当前节点是需要删除的节点 if(cur->val == val) { //首先保存下一个节点 struct ListNode* next = cur->next; //如果删除的为头节点，更新头节点 //否则让当前节点的前趋节点链接next节点 if(prev == NULL) { head = cur->next; } else { prev->next = cur->next; } //释放当前节点，让cur指向next free(cur); cur = next; } else { //如果cur不是需要删除的节点，则更新prev,cur prev = cur; cur = cur->next; } } return head; }
2.反转链表
解题思路：
1.链表逆置，将两个相邻的节点交换位置，交换n-1次，完成链表逆置。
代码段：
struct ListNode* reverseList(struct ListNode* head) { if(head == NULL || head->next == NULL) return head; struct ListNode* n1, *n2, *n3; n1 = head; n2 = n1->next; n3 = n2->next; n1->next = NULL; //中间节点不为空，继续修改指向 while(n2) { //中间节点指向反转 n2->next = n1; //更新三个连续的节点 n1 = n2; n2 = n3; if(n3) n3 = n3->next; } //返回新的头 return n1; }
2.头插法，从第一个节点开始遍历，作为新链表的尾节点，然后每遍历一个，头插该节点在新链表中。
// 取节点头插的思想完成逆置 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; //头插新节点，更新头 cur->next = newhead; newhead = cur; cur = next; } return newhead; }
3.找中间节点
解题思路：
快慢指针：给一个快指针与慢指针都是从链表的头节点开始遍历，快指针每次遍历两个节点，慢指针每次遍历一个节点，当快指针遍历结束时，慢指针刚好处于节点，返回慢指针。
这里需要考虑一下节点总数对于奇偶情况，若为奇数节点快指针刚好为NULL时，慢指针为中间。若为偶指针，则快指针的next为空时，慢指针为中间指针。
所以循环条件为两个都不为零时，即其中一个为零就是中间指针。
truct ListNode* middleNode(struct ListNode* head){ struct ListNode* faster=head; struct ListNode* fast=head; while(faster &&faster->next) { fast=fast->next; faster=faster->next->next; } return fast; }
4.找倒数第k个
解题思路：
与找中间节点的思路相同，当快指针指向第k个节点时，慢指针指向第一个节点，开始遍历，当快指针为NULL时，慢指针为该链表中倒数第k个节点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* fast=pListHead; struct ListNode* slow =pListHead; while(k--) { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }
5.合并两个有序链表
解题思路：
尾插法：因为是有序链表，我们直接从前开始比较：给定两个指针分别指向链表一与链表二，这里返回的时第三个新链表，则让第一个指针指向节点的数与第二个指针指向节点的数作比较，谁小谁先插，将较小的那个数的节点尾插在链表三之后，之后第一个指针与第二个指针同时继续往后遍历，等到其中一个先遍历完的时候，将另一个指针指向的节点直接尾插到链表三中。若某一链表为空，则返回另外一个。
struct ListNode* mergeTwoLists(struct ListNode*list1, struct ListNode* list2){ struct ListNode*p1=list1; struct ListNode*p2=list2; if(p1 == NULL) return p2; else if(p2 == NULL) return p1; struct ListNode* head = NULL, *tail = NULL; //创建空链表 head = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); tail->next = NULL; while(p1 && p2) { // 取小的进行尾插 if(p1->val < p2->val) { tail->next = p1; tail = tail->next; p1 = p1->next; } else { tail->next = p2; tail = tail->next; p2 = p2->next; } } //剩余元素直接拼接 if(p1) tail->next = p1; else tail->next = p2; struct ListNode* list = head->next; free(head); return list; }
6.链表分割
解题思路：
创建新链表时为了避免头节点判空这一繁琐的步骤，我们创建两个带哨兵位的链表，从已知链表头节点开始遍历，将小于x的该节点重新放在一个链表内，其余大于等于x按原顺序放在另一个链表内，之后free掉哨兵位，合并两个链表，尾节点置空，返回新头节点。
if(pHead == NULL) return NULL; struct ListNode* lessHead, *lessTail,*greaterHead, *greaterTail; //创建链表表头 lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = pHead; while(cur) { //小于x的尾插到lessTail if(cur->val < x) { lessTail->next = cur; lessTail = lessTail->next; } //大于等于x的尾插到greaterTail else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } //链接两个链表 lessTail->next = greaterHead->next; greaterTail->next = NULL; //获取表头 pHead = lessHead->next; free(lessHead); free(greaterHead); return pHead; }
7.链表的回文结构
解题思路：
所谓回文结构就是链表是否对称，因此我们首先需要找的中间节点，将中间节点前的存放在一个链表内，将中间节点包括在中间节点逆置后放在另一个链表中，两链表比对，若有其中一个不相等返回false,孙环结束后返回true。
对于链表奇偶情况时，无论奇偶带有中间节点的比较长，而逆置后与前半部分对比，要么刚好，要么提前结束，不影响对称性。
class PalindromeList { public: bool chkPalindrome(ListNode* A) { if (A == NULL || A->next == NULL) return true; ListNode* slow, *fast, *prev, *cur, *tmp; slow = fast = A; //找到中间节点 while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } prev = NULL; //后半部分逆置 cur = slow; while (cur) { tmp = cur->next; cur->next = prev; prev = cur; cur = tmp; } //逐点比对 while (A && prev) { if (A->val != prev->val) return false; A = A->next; prev = prev->next; } return true; } };
8.找公共节点
解题思路：本题可直接暴力求解，分别计算出A B两链表的长度，它们的长度差作为较长那个链表便利的条件，即两链表同长度开始比较，若相等则是公共节点，注意这里相同的是结点的地址。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* pa=headA; struct ListNode* pb=headB; int m=0,n=0; while(pa) { pa=pa->next; m ++; } while(pb) { pb=pb->next; n++; } int x=m-n; struct ListNode* a=headA; struct ListNode* b=headB; if(x>0) { while(x--) { a=a->next; } while(a) { if(a==b) { return a; } a=a->next; b=b->next; } }else if(x<0) { while(x++) { b=b->next; } while(b) { if(a==b) { return b; } a=a->next; b=b->next; } }else if(x==0) { while(a) { if(a==b) { return a; } a=a->next; b=b->next; } } return NULL; }
