練習

1. 刪除val節點

oj鏈接

這道題最先想出來的方法肯定是在遍歷鏈表的同時刪除等于val的節點，我們用第二中思路:不等于val的節點尾插，讓后返回新節點。代碼如下：

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newhead = NULL,*tail = NULL,*cur = head;//tail解決尾插每次都要找尾的問題while(cur){if(cur->val == val){struct ListNode* del = cur;cur = cur->next;free(del);}else{if(newhead == NULL){newhead = tail = cur;}else{tail->next = cur;tail = cur;}cur = cur->next;tail->next = NULL;}}return newhead;
}

2.返回中間節點

oj鏈接

找中間節點，利用快慢指針，快指針一次走兩步，慢指針一次走一步。快指針到終點，慢指針剛好走一半，慢指針走到的節點就是中間節點。唯一的區別就是偶數個節點和奇數個節點判斷結束的條件略有不同。

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

3.合并鏈表

oj鏈接

這道題的思路和第一題大同小異，就是小的尾插。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 ==NULL)return list2;if(list2 == NULL)return list1;    struct ListNode* head1 = list1;struct ListNode* head2 = list2;struct ListNode* newhead =NULL, *tail = NULL;while(head1 && head2){if(head1->val < head2->val){if(newhead == NULL){newhead = tail = head1;}else{tail->next = head1;tail = tail->next;}head1 = head1->next;}else{if(newhead == NULL){newhead = tail = head2;}else{tail->next = head2;tail = tail->next;}head2 = head2->next;}}if(head1){tail->next = head1;}if(head2){tail->next = head2;}return newhead;
}

4.反轉鏈表

oj鏈接

方法一： 頭插

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newhead = NULL;while(cur){struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;} return newhead;
}

方法二：每個節點挨個反轉

// 方法二：每個節點挨個反轉
struct ListNode* reverseList(struct ListNode* head) {if(NULL == head){return NULL;}struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next; }return n1;
}

5.鏈表分割

?oj鏈接

?這道題小于x的尾插一個鏈表，大于等于x的尾插另一個鏈表。最后把兩個鏈表連接起來。兩個鏈表使用帶哨兵位的頭結點會方便一些。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* lesshead,*lesstail,*greathead,*greattail;lesshead = lesstail =(struct ListNode*)malloc(sizeof(struct ListNode));greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while(cur){if(cur->val < x){lesstail->next = cur;lesstail = lesstail->next;}else {greattail->next = cur;greattail = greattail->next;}cur = cur->next;}lesstail->next = greathead->next;greattail->next = NULL;pHead = lesshead->next;free(lesshead);free(greathead);return  pHead;}
};

6.鏈表的回文結構?

oj鏈接

這道題先找到中間節點，再反轉中間節點后面的鏈表，之后再逐一對比即可。

struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow =head,*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head){struct ListNode* curr = head,*prev = NULL;while(curr){struct ListNode* tmp = curr->next;curr->next  =  prev;prev = curr;curr = tmp;}return  prev;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* mid =  middleNode(A);struct ListNode* rmid = reverseList(mid);while(rmid){if(A->val != rmid->val){return false;}else {A = A->next;rmid = rmid->next;}}return true;}
};

7.相交鏈表

oj鏈接?

?

?先判斷是否相交，計算兩鏈表的長度，長鏈表先走長度的差值，之后一起走找相交節點即可。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* list1 = headA;struct ListNode* list2 = headB;int len1 = 1,len2 = 1;while(list1->next){list1 = list1->next;++len1;}while(list2->next){list2 = list2->next;++len2;}if(list1 != list2){return NULL;}int len = abs(len1-len2);struct ListNode* shortlist = headA;struct ListNode* longlist =  headB;if(len1 > len2){shortlist = headB;longlist = headA;}while(len--){longlist = longlist->next;}while(longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next;}return shortlist;
}

8.環形鏈表

?oj鏈接

?

利用快慢指針解決，如果有環快慢指針會相遇。

bool hasCycle(struct ListNode *head) {struct ListNode* fast = head,*slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;while(fast == slow){return true;}}return false;
}

9.環形鏈表 ||

oj鏈接?

讓一個指針從鏈表起始位置開始遍歷鏈表，同時讓一個指針從判環時相遇點的位置開始繞環 運行，兩個指針都是每次均走一步，最終肯定會在入口點的位置相遇。

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast = head,*slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//帶環if(fast == slow){struct ListNode* meet = slow;while(head != meet){meet = meet->next;head = head->next;}return meet;}}return NULL;}

?證明：