网站备案资质,网站设计常用软件,网络推广工作,网页怎么赚钱文章目录反转链表合并两个有序链表删除重复元素反转链表
反转链表包括两种#xff0c;反转全部元素或者反转部分元素。在这里#xff0c;我们约定#xff1a;数据元素类型是struct LinkNode#xff0c;要反转链表的第一个节点是head#xff0c;head的前面一个节点是pre反转全部元素或者反转部分元素。在这里我们约定数据元素类型是struct LinkNode要反转链表的第一个节点是headhead的前面一个节点是pre如果head是首节点则pre等于NULL要反转链表的最后一个节点的后一个节点是p。 比如说我们要反转的是2543则head节点是2pre是7p是6如果反转的是972则head是9pre是NULLp是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-nextpre;pre head;headnext;}return pre;
}LeedCode 206. 反转链表反转全部元素反转全部元素最后一个节点的下一个节点是NULL。
struct ListNode* reverse(struct ListNode* head,struct ListNode *p){struct ListNode *prep;while(head!pre head!NULL){struct ListNode *next head-next;head-nextpre;prehead;headnext;}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 i1;ileft;i){pre curr;curr curr-next; }for(int ileft;iright;i){curr curr-next;}/*如果pre不等于NULL说明pre的下一个节点是首节点如果pre等于NULLhead就是要反转的首节点反转链表最后一个节点的后一个节点是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(list1NULL){return list2;}if(list2NULL){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(headNULL || head-nextNULL){return head;}//head head-valhead-next-val?head-next:head;head-next deleteDuplicates(head-next);return head-valhead-next-val?head-next:head;
}
