203.移除链表元素|707.设计链表|206.反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // ListNode* virtPoint = (ListNode*)malloc(sizeof(ListNode));
        ListNode* virtPoint = new ListNode(0);
        virtPoint -> next = head; 
        ListNode* p1 = virtPoint, *p2 = head, *q = nullptr;
        // ListNode* p2 = head -> next == null ? null : head -> next;
        while (p2 != NULL) {
            if (p2 -> val == val) {
                q = p2;
                p1 -> next = p2 -> next;
                p2 = p2 -> next;
                delete q;
                // p1 = p2;这里应该做条件判断
                // p2 = p2 -> next;
               
            } 
            else {
                p1 = p2;
                p2 = p2 -> next;
            }
        }
        return virtPoint -> next;
    }
};

• 707.设计链表
  • 注意结构体的定义以及私有变量和对象的初始化
  • 将指针delete后，不要忘记赋值为nullptr,否则tmp指针将会指向随机空间而不是空

    class MyLinkedList {
    public:
    	//结点结构体定义
        struct LinkedNode {
            int val;
            LinkedNode* next;
            LinkedNode(int val) : val(val), next(nullptr) {}
        };
    	//初始化链表
        MyLinkedList() {
            dummyHead = new LinkedNode(0);
            size = 0;
        }
        
        int get(int index) {
            if (index  (size - 1))  return -1;
            LinkedNode* cur = dummyHead -> next ;
            for (int i = index; i > 0; i--) {
                cur = cur -> next;
            }
            return cur -> val;
        }
        
        void addAtHead(int val) {
            LinkedNode* newNode = new LinkedNode(val);
            newNode -> next = dummyHead -> next;
            dummyHead -> next = newNode;
            size++;
        }
        
        void addAtTail(int val) {
            LinkedNode* newNode = new LinkedNode(val);
            LinkedNode* cur = dummyHead;
            while (cur -> next != nullptr) {
                cur = cur -> next;
            }
            cur -> next = newNode;
            // newNode -> next = nullptr;
            size++;
        }
        
        void addAtIndex(int index, int val) {
            if (index > size)  return;
            if (index  next;
            }
            newNode -> next = cur -> next;
            cur -> next = newNode;
            size++;
        }
        
        void deleteAtIndex(int index) {
            if (index = size) return;
            LinkedNode* cur = dummyHead;
            LinkedNode* tmp = nullptr;
            while (index--) {
                cur = cur -> next;
            }
            tmp = cur -> next;
            cur -> next = cur -> next -> next;
            delete tmp;
            size--;
        }
    private :
        int size;
        LinkedNode* dummyHead;
    };
    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * MyLinkedList* obj = new MyLinkedList();
     * int param_1 = obj->get(index);
     * obj->addAtHead(val);
     * obj->addAtTail(val);
     * obj->addAtIndex(index,val);
     * obj->deleteAtIndex(index);
     */
    

    • 206.反转链表
    • 学习思路如下图，双指针

      /**
       * Definition for singly-linked list.
       * struct ListNode {
       *     int val;
       *     ListNode *next;
       *     ListNode() : val(0), next(nullptr) {}
       *     ListNode(int x) : val(x), next(nullptr) {}
       *     ListNode(int x, ListNode *next) : val(x), next(next) {}
       * };
       */
      class Solution {
      public:
          ListNode* reverseList(ListNode* head) {
              ListNode* slow = nullptr;
              ListNode* quick = head;
              ListNode* tmp = nullptr;//用于存储快指针的next
              while (quick) {
                  tmp = quick -> next;
                  quick -> next = slow;
                  slow = quick;
                  quick = tmp;
              }
              return slow;
          }
      };