目录
移除链表元素
要想移除链表的元素，那么只需要将目标节点的前一个节点的next指针指向目标节点下一个节点的next指针
但是这里就会出现一个问题，如果头节点是目标值怎么办？
此时就有两种思路，一种就是分开讨论，当头节点为目标值时，头节点的next指针指向下一个节点，使下一个节点成为新的头节点
另一种就是创建虚拟头节点，这样在删除的时候就可以统一代码风格
思路1
不创建虚拟头节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
//头节点为目标值的情况
while(head!=NULL&&head->val==val)
{
head = head->next;
}
//处理完头节点为目标值的情况
ListNode* pcur = head;
while(pcur!=NULL&&pcur->next!=NULL)
{
if(pcur->next->val==val)
{
pcur->next = pcur->next->next;
}
else
{
pcur = pcur->next;
}
}
return head;
}思路2
创建虚拟头节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
//使用虚拟头节点dummyhead来进行删除操作
ListNode* dummyhead = (ListNode*)malloc(sizeof(ListNode));
dummyhead->next = head;
ListNode* pcur = dummyhead;
while(pcur&&pcur->next)
{
if(pcur->next->val==val)
{
pcur->next = pcur->next->next;
}
else
{
pcur = pcur->next;
}
}
return dummyhead->next;
}反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
ListNode* cur = head;
ListNode* prev = NULL;
ListNode* tmp = NULL;
while(cur)
{
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}让我们画一个图来解释这个代码
当我们遍历完这个链表之后，返回的prev就会依次从后往前返回链表中的元素了
寻找链表中间节点
这道题的思路是双指针法，一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表结尾时，慢指针的位置就是链表的中间节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}判断链表是否相交
如果要判断链表是否相交，那么就要分别遍历这两个链表，判断他们的尾节点的地址是否相同，其次再找到相交的位置的元素
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
int lenA = 1;
int lenB = 1;
ListNode* curA = headA;
ListNode* curB = headB;
while(curA->next)
{
curA = curA->next;
lenA++;
}
while(curB->next)
{
curB = curB->next;
lenB++;
}
//判断地址是否相等
if(curA!=curB)
{
return NULL;
}
//使用假设法
int gap = abs(lenA-lenB);
ListNode* longlist = headA;
ListNode* shortlist = headB;
if(lenB>lenA)
{
longlist = headB;
shortlist = headA;
}
//先让长指针走到短指针的位置，然后开始地址比较
while(gap--)
{
longlist = longlist->next;
}
while(shortlist!=longlist)
{
longlist = longlist->next;
shortlist = shortlist->next;
}
return shortlist;
}回文链表
回文链表的思路是先找到链表的中间节点，然后将中间节点后面的元素反转，再和前面的元素一个一个比较，如果都i相等，那么就是回文链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
bool isPalindrome(struct ListNode* head)
{
//先找到链表的中间元素
ListNode* slow = head;
ListNode* fast = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
//反转中间节点之后的元素
ListNode* cur = slow;
ListNode* prev = NULL;
ListNode* tmp = NULL;
while(cur)
{
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
while(head&&prev)
{
if(head->val!=prev->val)
{
return false;
}
prev = prev->next;
head = head->next;
}
return true;
}环形链表
判断是否为环形链表，依然是快慢指针的方法，非常简单，直接上代码了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}环形链表||
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
//判断是否有环
if(slow==fast)
{
ListNode* meet = head;
while(meet!=slow)
{
slow = slow->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}在这个代码中，我们将meet从head开始遍历，那么当meet和slow相遇的节点就是环形链表的入口处
那么我们如何证明呢？
