Leetcode常见链表问题及代码示例
按规定区间反转链表
思路：可以考虑成一种把前后数字的结点断开重新组合的问题
/**
*Definitionforsingly-linkedlist.
*structListNode{
*intval;
*ListNode*next;
*ListNode(intx):val(x),next(NULL){}
*};
*/
classSolution{
public:
ListNode*reverseBetween(ListNode*head,intm,intn){
ListNode*dummy=newListNode(-1),*pre=dummy;
dummy->next=head;
for(inti=0;inext;
ListNode*cur=pre->next;
for(inti=m;inext;
cur->next=t->next;
t->next=pre->next;
pre->next=t;
}
returndummy->next;
}
};
分割链表
思路：先找到一个大于或者等于给定值的节点，然后再逐个把小于他们的值放在前面。例如本例先找到4，然后再找到3，然后把小于3的值都放在其前面
/**
*Definitionforsingly-linkedlist.
*structListNode{
*intval;
*ListNode*next;
*ListNode(intx):val(x),next(NULL){}
*};
*/
classSolution{
public:
ListNode*partition(ListNode*head,intx){
ListNode*p=newListNode(-1);
p->next=head;
ListNode*pre=p,*cur=head;
while(pre->next&&pre->next->valnext;
cur=pre;
while(cur->next){
if(cur->next->valnext;
cur->next=tmp->next;
tmp->next=pre->next;
pre->next=tmp;
pre=pre->next;
}else{
cur=cur->next;
}
}
returnp->next;
}
};
逆序链表存储数相加
思路：先建立一个p结点，然后将相加生成的新结点按顺序放到p结点之后，然后再用一个新指针cur指向新链表的最后一位。设置一个进位计数res，当两个结点值相加之后，可以用sum/10来表示进位，然后以sum%10来建立新的结点。最后需要注意的是最高位的进位问题，所以while结束后要，如果res为1，则再建一个值为1的结点。
/**
*Definitionforsingly-linkedlist.
*structListNode{
*intval;
*ListNode*next;
*ListNode(intx):val(x),next(NULL){}
*};
*/
classSolution{
public:
ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){
ListNode*p=newListNode(-1),*cur=p;
intres=0;
while(l1||l2){
intval1=l1?l1->val:0;
intval2=l2?l2->val:0;
intsum=val1+val2+res;
res=sum/10;
cur->next=newListNode(sum%10);
cur=cur->next;
if(l1)
l1=l1->next;
if(l2)
l2=l2->next;
}
if(res)
cur->next=newListNode(1);
returnp->next;
}
};
顺序链表存储相加
思路：这道题和第2题类似，但是链表是从前往后遍历，加法却要从最低位相加，所以可以考虑改用栈来存储放进来的数据。
/**
*Definitionforsingly-linkedlist.
*structListNode{
*intval;
*ListNode*next;
*ListNode(intx):val(x),next(NULL){}
*};
*/
classSolution{
public:
ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){
stacks1,s2;
while(l1){
s1.push(l1->val);
l1=l1->next;
}
while(l2){
s2.push(l2->val);
l2=l2->next;
}
intsum=0;
ListNode*res=newListNode(0);
while(!s1.empty()||!s2.empty()){
if(!s1.empty()){
sum+=s1.top();
s1.pop();
}
if(!s2.empty()){
sum+=s2.top();
s2.pop();
}
res->val=sum%10;
ListNode*cur=newListNode(sum/10);
cur->next=res;
res=cur;
sum/=10;
}
returnres->val==0?res->next:res;
}
};
移除链表元素
思路：直接递归调用到链表末尾，然后回来，需要删除的元素将链表next指针指向下一个元素即好。
/**
*Definitionforsingly-linkedlist.
*structListNode{
*intval;
*ListNode*next;
*ListNode(intx):val(x),next(NULL){}
*};
*/
classSolution{
public:
ListNode*removeElements(ListNode*head,intval){
if(!head)returnNULL;
head->next=removeElements(head->next,val);
returnhead->val==val?head->next:head;
}
};
删除排序链表中的重复元素
思路：递归查找，如果head的值存在且相等，那么while循环跳过后面所有值相等的结点，如果后面if还有值相等则继续进行递归。如果最后到head的值不同后，返回到head即可。<这种方式比新建链表存储时间负责度高很多>
/**
*Definitionforsingly-linkedlist.
*structListNode{
*intval;
*ListNode*next;
*ListNode(intx):val(x),next(NULL){}
*};
*/
classSolution{
public:
ListNode*deleteDuplicates(ListNode*head){
if(!head)returnhead;
if(head->next&&head->val==head->next->val){
while(head->next&&head->val==head->next->val){
head=head->next;
}
returndeleteDuplicates(head->next);
}
head->next=deleteDuplicates(head->next);
returnhead;
}
};
删除顺序链表中的重复元素
思路：head结点的值和身后结点的值进行比较，如果值相同，则返回后面一个结点。最后回溯递归调用删除重复结点。
/**
*Definitionforsingly-linkedlist.
*structListNode{
*intval;
*ListNode*next;
*ListNode(intx):val(x),next(NULL){}
*};
*/
classSolution{
public:
ListNode*deleteDuplicates(ListNode*head){
if(!head||!head->next)returnhead;
head->next=deleteDuplicates(head->next);
return(head->val==head->next->val)?head->next:head;
}
};
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。