[数据结构与算法]数据结构与算法7（移除重复节点 ）

1 问题

?????????编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

1.1 示例???

    输入：[1, 2, 3, 3, 2, 1]

 ???输出：[1, 2, 3]

2 思路

2.1 遍历

?图1 遍历

2.2 递归

图2 递归

3 编程

3.1 遍历

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

                next = next->next;
            }

            head = head->next;
        }

        return dummy->next;

    }
};

3.2 递归

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

            next = next->next;
        }

        head->next = removeDuplicateNodes(head->next) ;

        return head;

    }
};