# 1. 移除链表元素

💝 思路：

💖 代码实现：

struct ListNode* removeElements(struct ListNode* head, int val){

struct ListNode*newHead=(struct ListNode*)malloc(sizeof(struct ListNode));
newHead->next=NULL;
struct ListNode*tail=newHead;
struct ListNode*cur=head;
while(cur)
{

if(cur->val!=val)
{

tail->next=cur;
tail=cur;
}
cur=cur->next;
}
tail->next=NULL;
return newHead->next;
}


# 2. 反转链表

💝 思路：

💖 代码实现：

struct ListNode* reverseList(struct ListNode* head){

struct ListNode*cur=head;
struct ListNode*rhead=NULL;
while(cur)
{

struct ListNode*next=cur->next;
cur->next=rhead;
rhead=cur;
cur=next;
}
return rhead;
}


# 3. 链表的中间节点

💝 思路：

💖 代码实现：
struct ListNode* middleNode(struct ListNode* head){

struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast!=NULL&&fast->next!=NULL)
{

fast=fast->next->next;
slow=slow->next;
}
return slow;
}


# 4. 链表中倒数第k个节点

💝 思路：

💖 代码实现：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {

// write code here
if(!pListHead)
return NULL;
struct ListNode*fast,*slow;
fast=slow=pListHead;
while(k--)
{

if(fast==NULL)
return NULL;
fast=fast->next;
}
while(fast)
{

fast=fast->next;
slow=slow->next;
}
return slow;
}


# 5. 合并两个有序链表

💝 思路：

💖 代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

struct ListNode*virhead=(struct ListNode*)malloc(sizeof(struct ListNode));
virhead->next=NULL;
struct ListNode*tail=virhead;
while(list1&&list2)
{

if(list1->val<list2->val)
{

tail->next=list1;
tail=tail->next;
list1=list1->next;
}
else
{

tail->next=list2;
tail=tail->next;
list2=list2->next;
}
}
if(!list1) tail->next=list2;
if(!list2) tail->next=list1;
return virhead->next;
}


# 6. 链表分割

💝 思路：

💖 代码实现：
class Partition {

public:
ListNode* partition(ListNode* pHead, int x) {

// write code here
struct ListNode*greaterHead,*greaterTail,*lessHead,*lessTail;
greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*cur=pHead;
while(cur)
{

if(cur->val<x)
{

lessTail->next=cur;
lessTail=lessTail->next;
}
else
{

greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
greaterTail->next=NULL;
lessTail->next=greaterHead->next;
pHead=lessHead->next;
return pHead;
}
};


# 7. 链表的回文结构

💝 思路：

💖 代码实现：
struct ListNode* middleNode(struct ListNode* head){

struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast!=NULL&&fast->next!=NULL)
{

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

struct ListNode*cur=head;
struct ListNode*rhead=NULL;
while(cur)
{

struct ListNode*next=cur->next;
cur->next=rhead;
rhead=cur;
cur=next;
}
return rhead;
}
class PalindromeList {

public:
bool chkPalindrome(ListNode* A) {

// write code here
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;
}
};


# 8. 相交链表

💝 思路：

💖 代码实现：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

struct ListNode*curA=headA,*curB=headB;
int lenA=0,lenB=0;
while(curA->next)
{

lenA++;
curA=curA->next;
}
while(curB->next)
{

lenB++;
curB=curB->next;
}
if(curA!=curB)
return NULL;
int gap=abs(lenA-lenB);
struct ListNode*longList=headA,*shortList=headB;
if(lenA<lenB)
{

longList=headB;
shortList=headA;
}
while(gap--)
{

longList=longList->next;
}
while(longList!=shortList)
{

longList=longList->next;
shortList=shortList->next;
}
return longList;
}


# 9. 环形链表

💝 思路：

💖 代码实现：

bool hasCycle(struct ListNode *head) {

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

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


# 10. 环形链表II

💝 思路一：

💝 思路二：

💖 代码实现(一)：
struct ListNode *detectCycle(struct ListNode *head) {

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

fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{

struct ListNode*meet=head;
while(meet!=slow)
{

meet=meet->next;
slow=slow->next;
}
return meet;
}
}
return NULL;
}


💖 代码实现(二)：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{

if (headA == NULL || headB == NULL)
{

return NULL;
}
struct ListNode* curA = headA, * curB = headB;
int lenA = 1;
//找尾节点
while (curA->next)
{

curA = curA->next;
++lenA;
}
int lenB = 1;
while (curB->next)
{

curB = curB->next;
++lenB;
}
if (curA != curB)
{

return NULL;
}
struct ListNode* longList = headA, * shortList = headB;
if (lenA < lenB)
{

longList = headB;
shortList = headA;
}
//长的链表先走差距步
int gap = abs(lenA - lenB);
while (gap--)
{

longList = longList->next;
}
//同时走找交点
while (longList != shortList)
{

longList = longList->next;
shortList = shortList->next;
}
return longList;
}
struct ListNode* detectCycle(struct ListNode* head){

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

slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{

//转换相交
struct ListNode* meet = slow;
struct ListNode* next = meet->next;
meet->next = NULL;
struct ListNode* entryNode = getIntersectionNode(head, next);
//恢复环
meet->next = next;
return entryNode;
}
}
return NULL;
}


# 11. 复制带随机指针的链表

💝 思路：

2> 通过源节点的random找到源节点的random所指向的结点，该结点的next结点即为拷贝的每一个结点的random结点所要指向的结点。

3> 将源节点后面所拷贝的结点全部解下来，然后将其链接成一个新的链表，再将原链表恢复，这道题目就大功告成了。

💖 代码实现：

struct Node* copyRandomList(struct Node* head) {

//将拷贝结点链接到源节点后面
struct Node*cur,*Next;
cur=head;
while(cur)
{

struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
Next=cur->next;
copy->val=cur->val;
cur->next=copy;
copy->next=Next;
cur=Next;
}
//设置拷贝节点
cur=head;
while(cur)
{

struct Node*copy=cur->next;
if(cur->random==NULL)
copy->random=NULL;
else
copy->random=cur->random->next;

cur=copy->next;
}
//解下拷贝的结点
cur=head;
struct Node*newHead=NULL;
struct Node*newTail=newHead;
while(cur)
{

struct Node*copy=cur->next;
cur->next=copy->next;
if(newHead==NULL){

newHead=copy;
newTail=newHead;
}else{

newTail->next=copy;
newTail=newTail->next;
}
cur=cur->next;
}
return newHead;
}


# 补充内容：浅谈顺序表和链表的区别

💖 下面我们来浅浅看一下链表和顺序表的区别(这里的链表指的是带头双向循环链表)

|
17天前
【数据结构OJ题】环形链表

23 3
|
17天前
|

【数据结构OJ题】设计循环队列

22 1
|
17天前
【数据结构OJ题】有效的括号

20 1
|
17天前
【数据结构OJ题】复制带随机指针的链表

23 1
|
17天前
【数据结构OJ题】环形链表II

11 1
|
17天前
【数据结构OJ题】相交链表

16 1
|
17天前
【数据结构OJ题】用栈实现队列

24 0
|
17天前
【数据结构OJ题】用队列实现栈

26 0
|
2月前
|

LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
23 0
|
2月前
|

LeetCode 题目 86：分隔链表
LeetCode 题目 86：分隔链表
25 2