链表练习1

链表练习

总体思路就是需要设置虚拟头节点。

1.删完节点记得释放内存。

2.遍历的条件需要时cur->next, 因为cur只是一个虚拟节点。

3.dummyHead指向原链表。确保返回头节点。cur负责移动删除链表结点。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;//将虚拟头节点指向head，方便后面的操作
        ListNode* cur = dummyHead;
        while(cur->next != NULL)
        {
            if(cur->next->val == val)
            {
                LisNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else
            {
                cur = cur->next;
            }

        }

        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

反转链表

思路：

不要忘记空指针。要想到null。

1.使用prev标记空，cur标记头指针，next1标记cur-next。三个指针一起往前移动，进行值的交换反转。

prev主要是记住cur的上一个元素。

next1主要是为了记住cur的下一个元素。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur != nullptr)
        {
          ListNode* next1 = cur->next;
          cur->next = prev;
          prev = cur;
          
          cur = next1;
        
        }
        return prev;
    }
};

头插法反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    
       
        ListNode* dummy = new ListNode(0);
       
        ListNode* cur = head;
        ListNode* p = dummy;
        while(cur != NULL)
        {
            ListNode* tmp = cur;
            cur = cur->next;
            tmp->next = p->next;//把原来头节点的next节点赋值给 这个新来的头节点tmp的next中。因为这是头插。
            p->next = tmp;//然后连接tmp。
        }
        return dummy->next;
    }
}

找到链表的中间结点

1.快慢指针法。只需遍历一遍。

2.先遍历一遍求节点数目，再遍历一遍得到中间节点。遍历两遍。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* cur = head;
        int count = 0;
        while(cur != nullptr)
        {
            cur = cur->next;
            count++;
        }
      count = count / 2;
        
     
        for(int i = 0; i < count; i++)
        {
             head = head->next;
        }

        return head;
    }
};