数据结构链表力扣例题AC（1）——代码以及思路记录（含链表本机调试tips）

链表力扣例题

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

AC

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

代码思想

快慢指针，fast指针和slow指针都指向head，fast指针每次走两步，slow指针每次走一步，当将整个链表都遍历了一遍以后，fast指向了尾部（总节点数为奇数时指向尾部节点，总节点数为偶数时指向尾部节点的后面也就是空指针），而此时slow指针刚好指向的是中间节点（总节点数为偶数时则为第二个中间节点），此时返回slow指针即可。

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

AC

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;

    while(cur != NULL)
    {
        if(cur->val == val)
        {
            struct ListNode* next = cur->next;
            if(prev)
                prev->next = next;
            else{
                head = next;
            }
            free(cur);
            cur = next;
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

代码思路

链表本机调试tips

在本机调试链表是需要数据，按照链表的定义来进行创建的话，正常还需要写尾插函数等，比较繁琐，本机调试其实可以直接malloc出来，将数据直接写成链表，如下：

struct ListNode* n1(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n2(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n3(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n4(struct ListNode*)malloc(sizeof(struct ListNode));

n1->va1 = 1;
n2->va1 = 2;
n3->va1 = 3;
n4->Va1 = 4;

n1->next n2;
n2->next n3;
n3->next n4;
n4->next NULL;

这样就是一个1->2->3->4->NULL的链表了