题目1:
本题力扣链接:https://leetcode.cn/problems/middle-of-the-linked-list/solutions/164351/lian-biao-de-zhong-jian-jie-dian-by-leetcode-solut/
思路1:单指针法
首先我们对链表进行遍历,记录链表的总长度N,再进行遍历原链表,返回刚跳出循环大于N/2时,对应的链表节点,即为中间节点。
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* pcur=head;if(head==NULL){return head;}int count=0;while(pcur){count++;pcur=pcur->next;}pcur=head;int k=0;while(k<count/2){k++;pcur=pcur->next;}return pcur;
}
思路2:快慢指针法
typedef struct ListNode ListNode ;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;}
场景1:
场景二:
题目2:
OJ链接:
思路1:反转链表+遍历
先将原链表进行翻转,再将反转后的链表的头结点移动k-1位,最后直接返回此时节点的值。
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){//1. 先将原链表进行翻转//2. 再将反转后的链表的头结点移动k-1位ListNode* n1,*n2,*n3;n1=NULL,n2=head,n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}k=k-1;while(k--){n1=n1->next;}return n1->val;
}
复杂度分析:
时间复杂度:O(N),其中N为给定链表节点的数目。
空间复杂度:O(1)
思路2:遍历+挪动
先计算原链表的总长度s,再将原链表的头结点移动s-k位,返回此时节点对应的值。
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){ListNode* pcur=head;int s=0;while(pcur){s++;pcur=pcur->next;}int m=s-k;while(m--){head=head->next;}return head->val;}
复杂度分析:
时间复杂度:O(N),其中N为给定链表节点的数目。
空间复杂度:O(1)
题目3:
思路:遍历+尾插+比较
创建新的带头链表,依次遍历两个原链表,比较对应的值,尾插到新的链表尾部。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}ListNode* newlist,*newhead;newhead=newlist=(ListNode*)malloc(sizeof(ListNode));while (list1 && list2) {if (list1->val > list2->val) {newlist->next = list2;list2 = list2->next;} else {newlist->next = list1;list1 = list1->next;}newlist = newlist->next;}if (list1)newlist->next = list1;if (list2)newlist->next = list2;return newhead->next;
}
如果本文章对你有帮助,期待你的三连!!!