我要评论
移除链表元素
题目链接：link
本题不同于基本操作中的头删尾删等，因为头结点也有可能是要删掉的，那这个时候就比较麻烦了，所以我们最好是重新定义一个链表，遍历原链表不为val的节点，尾插在新链表中。
/**
* definition for singly-linked list.
* struct listnode {
* int val;
* struct listnode *next;
* };
*/
struct listnode* create(int x)
{
struct listnode* new=(struct listnode*)malloc(sizeof(struct listnode));
new->val=x;
new->next=null;
return new;
}
void pushback(struct listnode** pp,int x,struct listnode** ppt)
{
struct listnode* new=create(x);
if(*pp==null)
{
*pp=new;
*ppt=new;
return;
}
(*ppt)->next=new;
(*ppt)=(*ppt)->next;
}
struct listnode* removeelements(struct listnode* head, int val) {
struct listnode* newhead=null;
struct listnode* tail=null;
struct listnode* cur=head;
while(cur!=null)
{
if(cur->val!=val)
pushback(&newhead,cur->val,&tail);
cur=cur->next;
}
return newhead;
}
另外官方题解用了递归迭代的方式也很值得学习：
迭代：
/**
* definition for singly-linked list.
* struct listnode {
* int val;
* struct listnode *next;
* };
*/
struct listnode* removeelements(struct listnode* head, int val) {
struct listnode* dummyhead=(struct listnode*)malloc(sizeof(struct listnode));
dummyhead->next=head;
struct listnode* cur=dummyhead;
while(cur->next!=null)
{
if(cur->next->val==val)
cur->next=cur->next->next;
else
cur=cur->next;
}
return dummyhead->next;
}
递归的话，反正我是理解的不太好（每次都得画好久递归图才能理解呜呜呜）
struct listnode* removeelements(struct listnode* head, int val) {
if (head == null) {
return head;
}
head->next = removeelements(head->next, val);
return head->val == val ? head->next : head;
}
链表的中间节点
题目链接：link
这道题的思路是：设置两个指针，一个slow指针，一个fast指针，slow指针一次走一步，fast指针一次走两步，当fast或fast的next为空的时候，slow就是我们要找的中间节点。
/**
* definition for singly-linked list.
* struct listnode {
* int val;
* struct listnode *next;
* };
*/
typedef struct listnode ln;
struct listnode* middlenode(struct listnode* head) {
ln* slow=head;
ln* fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
反转链表
题目链接：link
这道题的思路非常精巧。
设立三个指针，n1，n2和n3，分别指向null，头结点和头结点的next。
当n2不为空的时候，将n2的next指向n1，然后将n3赋值给n2（这也是n3存在的意义，因为改变n2的next指针以后，n2就无法通过n2=n2->next语句访问到原链表的下一个指针了）n3=n3->next，n1=n2；
/**
* definition for singly-linked list.
* struct listnode {
* int val;
* struct listnode *next;
* };
*/
typedef struct listnode ln;
struct listnode* reverselist(struct listnode* head) {
if(head==null)
return null;
if(head->next==null)
return head;
ln* n1=null;
ln* n2=head;
ln* n3=head->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3!=null)
n3=n3->next;
}
return n1;
}
当然n3也可以不用一开始就定义，也可以在循环中当做一个临时变量：
struct listnode* reverselist(struct listnode* head) {
struct listnode* prev = null;
struct listnode* curr = head;
while (curr) {
struct listnode* next = curr->next;//在这里设置n3，就不用单独考虑head是否为空或者只有一个节点的情况了
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
合并两个有序链表
题目链接：link
设置四个指针，l1遍历链表1，l2遍历链表2，newhead是新链表头结点（哨兵位），newtail是新链表尾指针，l1和l2比较，谁小谁尾插到newtail后，然后向后走一位，没有尾插的不动，直到l1或l2有一方为空，再把没有遍历完的那个链表的剩余部分直接尾插到newtail后面。
/**
* definition for singly-linked list.
* struct listnode {
* int val;
* struct listnode *next;
* };
*/
typedef struct listnode ln;
struct listnode* mergetwolists(struct listnode* list1, struct listnode* list2) {
ln* l1=list1;
ln* l2=list2;
ln* newhead=(ln*)malloc(sizeof(ln));
ln* tail=newhead;
if(l1==null&&l2==null)
return null;
while(l1&&l2)
{
if(l1->val<=l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
tail=tail->next;
}
if(l1==null)
{
tail->next=l2;
}
else
{
tail->next=l1;
}
return newhead->next;
}
分割链表
题目链接：link
大小链表法，新设两个链表一个放小的，一个放大的，然后最后把他们拼起来。
/**
* definition for singly-linked list.
* struct listnode {
* int val;
* struct listnode *next;
* };
*/
typedef struct listnode ln;
struct listnode* partition(struct listnode* head, int x){
ln* s=(ln*)malloc(sizeof(ln));
ln* b=(ln*)malloc(sizeof(ln));
ln* st=s;
ln* bt=b;
ln* cur=head;
while(cur)
{
if(cur->val<x)
{
st->next=cur;
st=st->next;
}
else
{
bt->next=cur;
bt=bt->next;
}
cur=cur->next;
}
bt->next=null;
st->next=b->next;
}
这个题要注意的是，最后在处理bt->next，也就是大链表的最后时一定要记得“封尾”，也就是要给他赋值为null，因为我们在把原链表中的节点挪到新的大小链表中的时候，连同他的next指针一起挪动了，那也就是说，如果不“封尾”，那么大链表的最后一个元素后还连着他在原链表中的后继元素。
好了今天的分享就结束了，马上又要期末考试啦！期中数据结构得了满分，希望期末可以继续保持下去！！！下学期就是真正的软工人啦~
发表评论