移除链表元素
思路：先要判断这个链表是不是空链表，如果是空链表就直接返回NULL，就可以
代码：
struct ListNode* removeElements(struct ListNode* head, int val){ if(head == NULL) { return NULL; } struct ListNode* cur = head; struct ListNode* newnode, *tail; newnode = tail = NULL; while(cur != NULL) { if(cur->val != val) { if(tail == NULL) { newnode = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } else { struct ListNode* next = cur->next; free(cur); cur = next; } } if(tail) { tail->next = NULL; } return newnode; }
注意：这个题最后需要注意的是tail的下一个应该也是NULL，否则就有可能将最后一个链表连接。
合并两个有序链表
思路：重新用一个新的链表头来表示节点，如果小于的数就入到链表当中。
代码：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1 == NULL) { return list2; } if(list2 == NULL) { return list1; } struct ListNode* head, *tail; head = tail = NULL; while(list1 && list2) { if(list1->val < list2->val) { if(tail == NULL) { head = tail = list1; }else { tail->next = list1; tail = tail->next; } list1 = list1->next; }else { if(tail == NULL) { head = tail = list2; }else { tail->next = list2; tail = tail->next; } list2 = list2->next; } } if(list1) { tail->next = list1; } if(list2) { tail->next = list2; } return head; }
链表的中间节点
思路：这个题目只需要根据速度差，一个指针的速度是另一个指针速度的二倍，当快的指针到达终点的时候，慢指针刚好到达中间节点。
代码：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode *fast, *slow; fast = slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
链表中的倒数第k个结点
思路：先让快的链表走k步，然后两个指针一起往后移动，如果快的指针到达最后，慢的指针就是最后的结果。
代码：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode *fast, *slow; fast = slow = pListHead; while(k) { if(fast == NULL) { return NULL; } fast = fast->next; k --; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }
反转链表
代码：
struct ListNode* reverseList(struct ListNode* head){ if(head == NULL) { return NULL; } struct ListNode* n1, *n2, *n3; n1 = NULL; n2 = head; n3 = n2->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) { n3 = n3->next; } } return n1; }
链表分割
对于最后一个数字，还有不同的情况考虑：
代码：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail; lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); lessTail->next = greaterTail->next = NULL; struct ListNode* cur = pHead; while(cur) { if(cur->val < x) { lessTail->next = cur; lessTail = lessTail->next; }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; } };
链表的回文结构
思路：直接找到中间节点，然后反转中间节点到最后的链表就可以。
代码：
struct ListNode* findMid(struct ListNode* A) { struct ListNode* slow = A, *fast = A; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } struct ListNode* reverse(struct ListNode* mid) { struct ListNode* n1 = NULL, *n2 = mid, *n3 = n2->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) { n3 = n3->next; } } return n1; } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here struct ListNode* mid = findMid(A); struct ListNode* rhead = reverse(mid); while(A && rhead) { if(A->val != rhead->val) { return false; } A = A->next; rhead = rhead->next; } return true; } };
相交链表
思路：找到两个其中长的一个链表，然后走差值步，一起走看是否有相等的地址。
代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA, *curB = headB; int lenA = 0, lenB = 0; //分别找到链表A和链表B的长度 while(curA) { lenA ++; curA = curA->next; } while(curB) { lenB ++; curB = curB->next; } //如果最后不相等，则绝对不存在公共节点 //如果相等，则一定存在公共节点 if(curA != curB) { return NULL; } int gap = abs(lenA - lenB); //假设A>B struct ListNode* LongList = headA, *ShortList = headB; if(lenB > lenA) { LongList = headB; ShortList = headA; } while(gap --) { LongList = LongList->next; } while(LongList != ShortList) { LongList = LongList->next; ShortList = ShortList->next; } return LongList; }
环形链表
思路：两个指针，一个指针每次跑一步，另一个指针每次跑两步，如果有环两个指针肯定能够相遇。
代码：
bool hasCycle(struct ListNode *head) { struct ListNode* slow = head, *fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { return true; } } return false; }
环形链表II(找到如环的节点)
结论：让一个指针从链表的起始位置开始遍历链表，同时让一个指针从判环相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
代码：
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head, *fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { struct ListNode* meet = slow; while(head != meet) { head = head->next; meet = meet->next; } return head; } } return NULL; }
复制带随机指针的链表
思路：
- 拷贝节点在源节点的后面
代码实现：
struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; while(cur) { struct Node* next = cur->next; struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; cur->next = copy; copy->next = next; cur = next; } }
- 设置拷贝节点的random
代码实现：
struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; while(cur) { struct Node* next = cur->next; struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; cur->next = copy; copy->next = next; cur = next; } //设置拷贝节点的random cur = head; while(cur) { struct Node* copy = cur->next; if(cur->next == NULL) { copy->random = NULL; }else { copy->random = cur->random->next; } cur = cur->next->next; } }
- 拷贝节点解下来，连接组成拷贝链表
代码实现：
struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; while(cur) { struct Node* next = cur->next; struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; cur->next = copy; copy->next = next; cur = next; } cur = head; while(cur) { struct Node* copy = cur->next; if(cur->random == NULL) { copy->random = NULL; }else { copy->random = cur->random->next; } cur = cur->next->next; } cur = head; struct Node* copyHead = NULL, *copyTail = NULL; while(cur) { struct Node* copy = cur->next; struct Node* next = copy->next; cur->next = next; if(copyTail == NULL) { copyHead = copyTail = copy; }else { copyTail->next = copy; copyTail = copyTail->next; } cur = next; } return copyHead; }
