链表OJ练习（1）

一、移除链表元素

本题为力扣原题203

题目介绍：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

列表中的节点数目范围在 0~10000内

1<=Node.val<=50

0<=val<=50

思路：利用双指针解决，struct ListNode*dst=NULL;struct ListNode*cur=head;利用指针cur便利整个链表。

注：需要考虑到要删除的是否是头节点。

让我们看看如何来实现：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*dst=NULL;struct ListNode*cur=head;while(cur){if(cur->val==val){//找到了，删除if(cur==head){head=cur->next;free(cur);cur=head;}else{dst->next=cur->next;free(cur);cur=dst->next;}}else {dst=cur;cur=cur->next;}}return head;
}

二、反转链表

本题为力扣原题206

题目介绍：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：利用三指针解决，指针n1和n2用来交换指向，至真n3用来找到下一个节点。

注：需要注意的是判断指针在什么情况下为空，避免利用空指针。n1最开始为空。

让我们看看如何来实现：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head)
{struct ListNode*n1;struct ListNode*n2;struct ListNode*n3;n1=NULL;n2=head;if(n2){n3=n2->next;}while(n2){n2->next=n1;//往后移动n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}

三、链表的中间节点

本题为力扣原题876

题目介绍：

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点

思路：快慢指针，快指针每次走两步，慢指针每次走一步，当快指针到达尾部时，慢指针刚好到达中间节点

让我们看看如何来实现：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///快慢指针
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* falst;struct ListNode* slow;falst=head;slow=head;while(falst&&falst->next){slow=slow->next;falst=falst->next->next;}return slow;
}

四、返回倒数第k个节点

题目介绍;

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

思路：和上面一题很相似，还是用快慢指针，只不过这次是让，快慢指针都开始指向头节点，让快指针先走k步，然后慢指针和快指针在同时往后走，当快指针到达尾的时候，慢指针就指向了倒数第k个元素了。

注：这里需要注意的是k的大小，当k大于链表长度是就会溢出，这里我们直接返回NULL。

让我们看看如何来实现：

/*** struct ListNode {*	int val;*	struct ListNode *next;* };*/
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead ListNode类 * @param k int整型 * @return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) 
{if(pHead==NULL){return NULL;}struct ListNode*slow=pHead;struct ListNode*falst=pHead;int len=0;while(pHead){len++;pHead=pHead->next;}if(k>len){return NULL;}while(k){falst=falst->next;k--;}while(falst){falst=falst->next;slow=slow->next;}return slow;
}

五、合并两个有序链表

题目介绍：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：首先先考虑特殊情况，当链表一为空是返回链表二，链表二为空时返回链表一。然后我们开始遍历链表一和链表二，比较两个指针指向链表的元素大小，创建一个新链表头节点，将小的元素的节点尾插到新链表上，然后将较小元素的指针后移，然后在比较......如果最后链表一遍历完了，就可以将指向链表二的指针指向新链表的尾部，最后然会新链表的头节点。

注：题目时不带头节点的，所以我们创建玩心链表的头节点需要销毁，头指针指向头节点的下一个节点。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode*tail=NULL;struct ListNode*head=NULL;head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));while(list1&&list2){if(list2->val>list1->val){tail->next=list1;tail=tail->next;list1=list1->next;}else{tail->next=list2;tail=tail->next;list2=list2->next;}   }if(list1){tail->next=list1;}if(list2){tail->next=list2;}struct ListNode* del=head;head=head->next;free(del);return head;
}