反轉鏈表

反轉鏈表包括兩種，反轉全部元素或者反轉部分元素。在這里，我們約定：數據元素類型是struct LinkNode，要反轉鏈表的第一個節點是head，head的前面一個節點是pre，如果head是首節點，則pre等于NULL，要反轉鏈表的最后一個節點的后一個節點是p。
比如說我們要反轉的是2，5，4，3，則head節點是2，pre是7，p是6；如果反轉的是9，7，2，則head是9，pre是NULL，p是3.

下面函數返回值是反轉鏈表后的首節點，head是要反轉鏈表的首節點，p是要反轉鏈表的最后一個節點的后一個節點。

struct LinkNode *reverse(struct LinkNode *head,struct LinkNode*p)
{struct LinkNode *pre = p;while(head!=p){struct LinkNode *next = head->next;head->next=pre;pre = head;head=next;}return pre;
}

LeedCode 206. 反轉鏈表反轉全部元素，反轉全部元素最后一個節點的下一個節點是NULL。

struct ListNode* reverse(struct ListNode* head,struct ListNode *p){struct ListNode *pre=p;while(head!=pre &&head!=NULL){struct ListNode *next = head->next;head->next=pre;pre=head;head=next;}return pre; 
}struct ListNode* reverseList(struct ListNode* head){return reverse(head,NULL);
}

LeedCode 92. 反轉鏈表 II反轉部分鏈表。

struct ListNode* reverseList(struct ListNode* head,struct ListNode *p){struct ListNode *pre = p;struct ListNode *curr = head;while(head!=p){struct ListNode *next = head->next;head->next = pre;pre = head;head = next;}return pre;
}/**
找到要反轉鏈表的首節點以及最后一個節點的后一個節點。
*/
struct ListNode* reverseBetween(struct ListNode* head, int left, int right){struct ListNode *pre = NULL;//pre：要反轉鏈表的前一個元素struct ListNode *curr = head;//curr：要反轉鏈表的最后一個元素for(int i=1;i<left;i++){pre = curr;curr = curr->next; }for(int i=left;i<right;i++){curr = curr->next;}/*如果pre不等于NULL，說明pre的下一個節點是首節點，如果pre等于NULL，head就是要反轉的首節點，反轉鏈表最后一個節點的后一個節點是curr->next*/if(pre!=NULL){pre->next = reverseList(pre->next,curr->next);return head;}else{return reverseList(head,curr->next);}
}

合并兩個有序鏈表

21. 合并兩個有序鏈表
使用遞歸思路。

/*
函數返回值是兩個鏈表按照遞增合并后的鏈表
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}if(list1->val <list2->val){list1->next = mergeTwoLists(list1->next,list2);return list1;}else{list2->next = mergeTwoLists(list1,list2->next);return list2;}
}

刪除重復元素

struct ListNode* deleteDuplicates(struct ListNode* head){if(head==NULL || head->next==NULL){return head;}//head = head->val==head->next->val?head->next:head;head->next = deleteDuplicates(head->next);return head->val==head->next->val?head->next:head;
}