单链表的经典算法OJ

目录

1.反转链表

2.链表的中间节点

3.移除链表元素

———————————————————————————————————————————

正文开始

1.反转链表

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //判空
    if(head == NULL)
        return head;
    //创建3个指针
    ListNode* n1,*n2,*n3;
    n1 = NULL; n2 = head; n3 = n2->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }
    return n1;
}

2.链表的中间节点

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

3.移除链表元素

 //创建新链表，pcur不为val则尾插到新链表中
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建一个空链表
    ListNode* newHead, * newTail;
    newHead = newTail = NULL;

    //遍历原链表
    ListNode* pcur = head;
    while (pcur)
    {
        //找值不为val的节点,尾插到新链表中
        if (pcur->val != val)
        {
            //链表为空
            if (newHead == NULL)
            {
                newHead = newTail = pcur;
            }
            else {
                //链表不为空
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    if (newTail)
        newTail->next = NULL;
    return newHead;
}

———————————————————————————————————————————

完