数据结构(01)—

数据结构(01)——链表OJ

移除链表元素

思路1

不创建虚拟头节点

思路2

创建虚拟头节点

反转链表

寻找链表中间节点

判断链表是否相交

回文链表

环形链表

环形链表||

移除链表元素

. - 力扣（LeetCode）

要想移除链表的元素，那么只需要将目标节点的前一个节点的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;
}

反转链表

206. 反转链表 - 力扣（LeetCode）

/**
 * 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就会依次从后往前返回链表中的元素了

寻找链表中间节点

这道题的思路是双指针法，一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表结尾时，慢指针的位置就是链表的中间节点

876. 链表的中间结点 - 力扣（LeetCode）

/**
 * 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;
}

判断链表是否相交

如果要判断链表是否相交，那么就要分别遍历这两个链表，判断他们的尾节点的地址是否相同，其次再找到相交的位置的元素

. - 力扣（LeetCode）

/**
 * 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;
}

环形链表

. - 力扣（LeetCode）

判断是否为环形链表，依然是快慢指针的方法，非常简单，直接上代码了

/**
 * 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相遇的节点就是环形链表的入口处

那么我们如何证明呢？