链表OJ--上

---

前言

一、反转链表

力扣206：反转链表- - -点击此处传送

思路图：
方法一：改变指向

方法二：

代码：

//方法一
//改变指向
struct ListNode* reverseList(struct ListNode* head) {//判断空if(head==NULL){return NULL;}struct ListNode*n1,*n2,*n3;n1=NULL;n2=head;n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}//方法二
//头插
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newhead = NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

二、移除链表元素

力扣203：移除链表元素- - -点击此处传送

思路图：

方法2：
当然这题也可以使用带哨兵位的结点

代码

//方法1：
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*cur=head;struct ListNode*newhead=NULL;struct ListNode*tail=NULL;while(cur){if(cur->val!=val){if(tail==NULL){newhead=tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{struct ListNode*tmp=cur;cur=cur->next;free(tmp);}}if(tail)tail->next=NULL;return newhead; 
}//方法2:
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur=head;struct ListNode* tail=NULL;struct ListNode* newhead=NULL;//哨兵位newhead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));while(cur){if(cur->val!=val){//尾插tail->next=cur;tail=tail->next;cur=cur->next;}else{struct ListNode*tmp=cur;cur=cur->next;free(tmp);}}tail->next=NULL;struct ListNode*tmp=newhead;newhead=newhead->next;free(tmp);return newhead;
}

三、链表中倒数第K个结点

牛客网：链表中倒数第K个结点- - -点击此处传送

思路图：

代码：

//牛客网代码模型
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* fast=pListHead;struct ListNode* slow=pListHead;while(k--){//空链表if(fast==NULL)return NULL;fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}

四、相交链表

力扣160：相交链表- - -点击此处传送

思路图：

代码：

//思路2：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode*curA=headA;struct ListNode*curB=headB;int lenA=0;int lenB=0;//计算链表A的长度while(curA->next){lenA++;curA=curA->next;}//计算链表B的长度while(curB->next){lenB++;curB=curB->next;}//无交点if(curA!=curB){return NULL;}//用绝对值求出差值int n=abs(lenA-lenB);struct ListNode*longList=headA;struct ListNode*shortList=headB;//若B长if(lenB>lenA){//长链表为BlongList=headB;//短链表为AshortList=headA;}//让长链表B先走差值while(n--){longList=longList->next;}//两链表一起走while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;
}

五、链表的中间结点

力扣876：链表的中间结点- - -点击此处传送

思路图：

代码：

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