反轉鏈表

1、題目：


2.思路
?思路1：建立一個newHead,取一個節(jié)點進行頭插。具體做法如下！

建立一個newHead(新頭)，由于一個節(jié)點里面存的是下一個節(jié)點的地址，如果取一個節(jié)點下來進行頭插，那么，要取的下一個節(jié)點的地址找不到，因此定義n1,n2,n1用來往下拿結點進行頭插，n2預備下一次要的節(jié)點 ，代碼如下！！！

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL){return NULL;}struct ListNode* newHead = NULL;//n1為向下取得插入的節(jié)點struct ListNode* n1 = head;//n2是給n1準備的節(jié)點struct ListNode* n2 = head->next;while(n1){n1->next = newHead;newHead = n1;n1 = n2;//當n2為NULL時，n2沒有取得節(jié)點了if(n2){n2 = n2->next;}}return newHead;
}

?思路2：把指針翻轉，把指針反轉的意思是，把存節(jié)點的地址交換，定義三個指針n1,n2,n3,n1 = NULL,n2 = head,n3 = head->next,n2為第一個節(jié)點翻轉，n2->next = n1,n2里面原來存的地址找不到，因此要n3存下一個節(jié)點的地址，這樣這個題就可以反轉了！！！

struct ListNode* reverseList(struct ListNode* head) {if(head == NULL){return NULL;}struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = head->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}return n1;
}

合并兩個有序鏈表

1、題目：

2、思路：
??這個題建立一個新鏈表，取小的數尾插即可，這兒有一些技巧，可以建立一個頭結點，直接尾插，這樣就省去了考慮newHead為NULL的情況，這個方法，在一些題中有妙用！！！``

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1==NULL){return l2;}if(l2==NULL){return l1;}//處理這個，建立一個頭節(jié)點，把為NULL的一種可能性去掉struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail= tmp;while(l1&&l2){if(l1->val<l2->val){tail->next = l1;tail = l1;l1 = l1->next;}else{tail->next = l2;tail = l2;l2 = l2->next;}}if(l1){tail->next = l1;}if(l2){tail->next = l2;}return tmp->next;
}

下面是一個正常的做法！！！

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1 ==NULL){return l2;}if(l2 == NULL){return l1;}struct ListNode* newHead,*tail;newHead  = NULL;while(l1&&l2){if(l1->val<l2->val){if(newHead == NULL){newHead = tail = l1;}else{tail->next = l1;tail = l1;}l1 = l1->next;}else{if(newHead == NULL){newHead = tail = l2;}else{tail->next = l2;tail = l2;}l2 = l2->next;}}if(l1){tail->next = l1;}if(l2){tail->next = l2;}return newHead;
}

分割鏈表

1、題目：

2、思路：
?建立兩個鏈表，一個是<x的鏈表，一個是>=x的鏈表，最后把這兩個鏈表組合起來，返回頭即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///建立兩個鏈表
//一個小于x
//一個大于等于x
struct ListNode* partition(struct ListNode* head, int x){/*  if（head == NULL）{return NULL;}*/struct ListNode* litterHead = ( struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* litterTail = litterHead;struct ListNode* biggerHead = ( struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* biggerTail = biggerHead;struct ListNode* cur = head;while(cur){if(cur->val<x){litterTail->next =cur;litterTail = cur;cur = cur->next;}else{biggerTail->next = cur;biggerTail = cur;cur = cur->next;}}biggerTail->next = NULL;litterTail->next = biggerHead->next;return litterHead->next;
}

完結！！！