数据结构--单链表OJ题

1.移除链表元素

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
//哨兵位
struct ListNode* newhead=malloc(sizeof(struct ListNode));

while(cur->next)
{
//判断下一个的值
if(cur->next->val==val)
{
cur->next=cur->next->next;
}
else{
cur=cur->next;
}

}
//返回头指针
}

2.反转链表

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//特殊条件
{
return NULL;
}
struct ListNode* prev=NULL;
//移动指针
while(cur)
{
cur->next=prev;
prev=cur;
cur=next;
//判断next
if(next!=NULL)
{
next=next->next;
}

}
return prev;
}

3.链表的中间结点

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head){
//先确定链表长度
int i=0;
while(node!=NULL)
{
node=node->next;
i++;
}
//确定中间节点位置
int k=i/2;
for(int i=0;i<k;i++)
{
}
}

struct ListNode* middleNode(struct ListNode* head){
//快慢指针
struct ListNode* slow,*fast;
//移动
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}

4.链表中的倒数第k个结点

/**
* struct ListNode {
*  int val;
*  struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
{
return NULL;
}
//利用相对距离
struct ListNode* slow,*fast;
//先走k步
while(k&&fast)
{
fast=fast->next;
k--;
}
if(k>0)
{
return NULL;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}

5.合并两个有序链表

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//哨兵位
struct ListNode* prehead=malloc(sizeof(struct ListNode));
//比大小
while(list1&&list2)
{
if(list1->val<list2->val)
{
prev->next=list1;
list1=list1->next;
prev=prev->next;
}
else
{
prev->next=list2;
list2=list2->next;
prev=prev->next;
}
}
//判断哪个链表有剩余
prev->next=list1==NULL?list2:list1;
}

6.链表分割

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* prevHead1=(struct ListNode*)malloc(sizeof(ListNode));
struct ListNode* prevHead2=(struct ListNode*)malloc(sizeof(ListNode));

{
{
tail1=tail1->next;
}
else {
tail2=tail2->next;
}
}
//连接
//尾置空
tail2->next=NULL;
}
};

7.链表的回文结构

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head){
//快慢指针
struct ListNode* slow,*fast;
//移动
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head){
//特殊条件
{
return NULL;
}
struct ListNode* prev=NULL;
//移动指针
while(cur)
{
cur->next=prev;
prev=cur;
cur=next;
//判断next
if(next!=NULL)
{
next=next->next;
}

}
return prev;
}
bool chkPalindrome(ListNode* head) {
ListNode* rmid=reverseList(mid); //中间位置后面倒置
//比较
while(rmid)
{
{
return false;
}
rmid=rmid->next;
}
return true;
}
};

8.相交链表

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int lenthA=1,lenthB=1;
//计算链表长度
while(curA->next)
{
++lenthA;
curA=curA->next;
}
while(curB->next)
{
++lenthB;
curB=curB->next;
}
//尾节点判断，不一样说明没有香蕉
if(curA!=curB)
{
return NULL;
}
//长度先走差距步
int abs=fabs(lenthA-lenthB);
if(lenthA<lenthB)
{
}
while(abs--)
{
longList=longList->next;
}
//找到相同的交点
while(longList!=shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
}

9.环形链表

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
//快慢指针
//赛道追逐问题
while(fast&&fast->next)
{

fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
return  true;
}

}
return false;
}

10.环形链表II

fast指针走的距离是slow指针的2倍，所以fast指针会先进入环中， fast可能会在环中绕几圈，我们设为n

fast指针走的距离为L+n(n>=1)*C+X,fast指针要追上slow，至少要绕一圈环

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
//快慢指针
struct ListNode* fast,*slow;
//有环
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
//相遇点
if(fast==slow)
{
struct ListNode* meet=fast;
{
meet=meet->next;
}
return meet;
}
}
return NULL;
}

|
26天前
|

[数据结构]——单链表——超详解
[数据结构]——单链表——超详解
36 0
|
11天前
|

8 0
|
11天前
|

10 0
|
21天前
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列.
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列
26 3
|
21天前
（数据结构）单链表 —— 尾插，尾删，头插，头删，查找，插入，删除。

24 0
|
21天前
|

【数据结构】单链表代码实现
【数据结构】单链表代码实现
11 1
|
21天前
|
Java
DAY-1 | Java数据结构之链表：删除无头单链表中等于给定值 val 的所有节点

26 0
|
26天前

17 0
|
28天前
|

28 1
|
28天前
|

10 1