LeetCode 203 Remove Linked List Elements（移除链表元素）（Linked List）（*）

版权声明：转载请联系本人，感谢配合！本站地址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50598373

翻译

从一个链表中移除所有值为val的元素。

例如
给定：1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6， val = 6
返回：1 --> 2 --> 3 --> 4 --> 5           

原文

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5           

分析

昨天中午收到一个好消息于是许久不能平静，反反复复这题一直错误，越改越混乱，毕竟逻辑已经在九霄云外了……

卧槽，这博客写的，啥好消息啊！我自己都好奇了……（2016/08/13更新）
           

今早删了昨天的代码重新来过，一次通过。

我新设置了3个索引：

newHead，指向头部，用于最后返回
pre，指向移动中节点的前一个节点
cur，指向移动中的节点           

我就不画图了……通过cur的不断循环，while内部判断cur的值是否与给定的val相等，分别作相应操作。最后pre和cur都移动到链表后面了，返回整个链表的重任就交给了newHead了。

还有一个关键问题是，上面的方法是从链表第二个节点开始与val作比较，那么第一个节点呢？昨天的思路现在想想真是太繁琐了，昨天是用了两个while循环，第二个就是上文说到，第一个用于判断链表头部的元素是否和val相等。

但是更好的方法是直接使用newHead。之前不是对链表第二个元素到最后一个元素做了判断嘛，返回的时候直接返回newHead或newHead的下一个元素不就好了？

代码

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head) return NULL;
        ListNode *pre = head, *cur = head->next, *newHead = pre;
        if (!cur) return pre->val == val ? NULL : pre;
        while (cur) {
            if (cur->val == val) pre->next = cur->next;
            else pre = pre->next;
            cur = cur->next;
        }
        if (newHead->val == val) return newHead->next;
        else return newHead;;
    }
};           

分析2

updated at 2016/08/13

其实几个月过去后，就发现原来的办法太复杂了，相比于现在的解法不仅多使用了一个变量，还多了2个if语句。

不过整体思路是一样的，只不过这里使用了新的head，就不会担心无法删除原本head的第一个节点了。

代码2

/**                                                                                                                                                                                            
 * Definition for singly-linked list.                                                                                                                                                          
 * struct ListNode {                                                                                                                                                                           
 *     int val;                                                                                                                                                                                
 *     ListNode *next;                                                                                                                                                                         
 *     ListNode(int x) : val(x), next(NULL) {}                                                                                                                                                 
 * };                                                                                                                                                                                          
 */
class Solution {
public:
  ListNode* removeElements(ListNode *head, int val) {
    if (head == NULL) return head;
    ListNode *newHead = new ListNode(0), *prev = newHead;
    newHead->next = head;
    while (prev && prev->next) {
      if (prev->next->val == val) {
        prev->next = prev->next->next;
      } else {
        prev = prev->next;
      }
    }
    return newHead->next;
  }
};