【数据结构初阶】详解链表OJ题

一.删除链表中等于给定值的节点

我们先来看第一题(题目链接):

因为我们需要从链表中删除满足条件的值，所以必须使用两个指针一个用来遍历链表，另一个记录上一个节点的位置。接着我们以遍历链表的指针不为空为循环条件编写代码，当当前节点的val值不等于给定x值时，就向下遍历，否则移除当前位置的节点。需要注意的一个特殊情况就是，链表第一个节点的值就等于给定的x值时，就需要移动头节点。代码如下:

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*prev =NULL,*cur=head;while(cur){if(cur->val != val){prev=cur;cur=cur->next;}else {if(prev == NULL){head=cur->next;free(cur);cur=head;}else{prev->next=cur->next;free(cur);cur=prev->next;}}}return head;
}

二.合并有序链表并返回

我们接着看下一题(题目链接)

这题的思路我们可以新malloc一个链表，然后定义两个指针指向链表的头节点，然后遍历比较两个给的链表的val数值，将较小的插入到新链表中。最后返回即可。代码如下:

truct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode*nextnode =(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur=nextnode;struct ListNode* head=nextnode;if(!list1)return list2;else if(!list2)return list1;else{while(list1&&list2){if(list1->val<list2->val){cur->next=list1;cur=cur->next;list1=list1->next;cur->next=NULL;}else{cur->next=list2;cur=cur->next;list2=list2->next;cur->next=NULL;}}if(list1)cur->next=list1;if(list2)cur->next=list2;return head->next;}
} 

三.链表的回文结构

1.反转单链表

我们看一下反转链表这一题(题目链接)

这题我们定义三个指针prev用来保存上一个节点的地址，初始化为NULL，curr初始化指向链表的头节点用来遍历链表，next用来保存遍历中下一个节点即可，代码如下，大家理解一下:

struct ListNode* reverseList(struct ListNode* head){struct ListNode*prev=NULL;struct ListNode*curr=head;while(curr){struct ListNode*next=curr->next;curr->next=prev;prev=curr;curr=next;}return prev;
}

2.返回非空链表的中间节点

(题目链接)

这题有个妙招------快慢指针，我们定义fast slow两个指针都指向头节点，不同的是快指针一次走两步而慢指针一次只走一步。考虑到链表是偶数个还是奇数个的问题，当快指针或者快指针的下一个节点走到NULL时，慢指针就走到了链表的中间节点，代码如下:

struct ListNode* middleNode(struct ListNode* head){struct ListNode*slow,*fast;slow=fast=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}

基于上面两题的讲解我们来看下这题(题目链接)

这题我们的思路就是找到链表的中间节点后，反转后半段链表后，与前半段链表进行比较，如果在遍历走到空指针之前，全部相同则就是回文结构。
代码如下:

class PalindromeList {public:struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow, *fast;slow = fast = head;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;}return slow;}bool chkPalindrome(ListNode* A) {struct ListNode*mid= middleNode(A);struct ListNode* rhead=reverseList(mid);while(A && rhead){if(A->val != rhead->val)return false;A=A->next;rhead=rhead->next;}return true;}
};

四.输出链表倒数第K个节点

我们看下题目(题目链接)

这题使用快慢指针的话也是非常简单，我们定义快慢指针指向链表头节点，然后先让快指针走k步后再让快慢指针同时走，等快指针走到空指针时，满指针就走到了倒数第K个节点。
代码如下:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow=pListHead;struct ListNode* fast=pListHead;while(k--){if(fast == NULL)return NULL;fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return slow;
}

五.基于给定值x分割单链表

我们看下一题(题目链接)

这题我们可以新malloc两个节点然后以给定值x将链表分割到两个链表中，最后将两个链表串起来即可。

代码如下:

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode*guard1,*guard2,*tail1,*tail2;tail1=guard1=(ListNode*)malloc(sizeof(ListNode*));tail2=guard2=(ListNode*)malloc(sizeof(ListNode*));tail1->next=tail2->next=NULL;ListNode* cur=pHead;while(cur){if(cur->val<x){tail1->next=cur;cur=cur->next;tail1=tail1->next;}else {tail2->next=cur;cur=cur->next;tail2=tail2->next;}}tail1->next=guard2->next;tail2->next=NULL;return guard1->next; }
};

六.返回两个链表的第一个中间节点

我们先看一下题目(题目链接)

做这题时我们要想清楚，如果两个链表有相交的节点，那再这节点后两个链表都指向同一个地址

上图这种情况是不存在的
所以我们可以得知两个有相交节点的链表最后的节点的地址是相等的(当然相交节点后都相同，只因在单链表中尾节点比较好找)

代码如下:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len1,len2;len1=len2=1;struct ListNode *tail1=headA;struct ListNode *tail2=headB;while(tail1){tail1=tail1->next;len1++;}while(tail2){tail2=tail2->next;len2++;}if(tail1 !=tail2)return NULL;int gap=abs(len1-len2);struct ListNode *longhead=headA;struct ListNode *shorthead=headB;if(len2>len1){longhead=headB;shorthead=headA;}while(gap--)longhead=longhead->next;while(shorthead != longhead){shorthead=shorthead->next;longhead=longhead->next;}return longhead;
}