专题训练-链表

• 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

需求分析：

• 需要排除掉链表为空的情况
• 当下一个节点为空时，不能进行访问，否则程序会崩溃
• 两个节点的值进行比较，如果相等执行对应的代码块，否则执行另一个代码块
• 两处地方需要i返回头指针

程序设计：

代码实现

ListNode* deleteDuplicates(ListNode* head) {
    
     if (!head) {
    
         return head;
     }
     ListNode* cur = head;
     while (cur->next) {
    
         if (cur->val == cur->next->val) cur->next = cur->next->next;
         else cur = cur->next;
     }
     return head;
}

• 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

需求分析：

• 相交说明指向的地址一样，可以利用这个特点来检测是否存在相交

程序设计

代码实现

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
      unordered_set<ListNode *> visited;
      ListNode *temp = headA;
      while (temp != nullptr) {
    
          visited.insert(temp);
          temp = temp->next;
      }
      temp = headB;
      while (temp != nullptr) {
    
          if (visited.count(temp)) {
    
              return temp;
          }
          temp = temp->next;
      }
      return nullptr;
};

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

需求分析：

• 删除：在链表中就是把地址域指向下一个节点

程序设计：

• 利用**栈+递归(自己调自己)**思想
• 重复执行CALL函数的终止条件是节点的指针域为NULL
• 第一次函数的返回都会把最后一个节点的指针域置空，然后每一次的ret都会进行比较，来决定上一个节点的下一个节点是谁

ListNode* removeElements(ListNode* head, int val) {
    
      if (head == nullptr) {
    
          return head;
      }
      head->next = removeElements(head->next, val);
      return head->val == val ? head->next : head;
}