链表-删除链表中重复的结点(思路和代码实现)

KLQ 2020-04-14 15:22:39 java常见问答 4590

大家对于链表都熟悉吗?下面要给大家分享的是删除链表中重复的结点的思路和代码实现,一起来具体的了解一下吧。

题目:

在一个排序的链表当中,存在着重复的结点,请删除掉这个链表中重复的结点,重复的结点不保留,返回链表头指针。

例:链表1->2->3->3->4->4->5 处理后为 1->2->5

思路1:

非递归的代码:

一、 首先要添加一个头节点,方便碰到第一个,第二个节点就相同的情况。

二、设置pre,last指针, pre指针指向现在确定不重复的那个节点,而last指针相当于工作指针,一直朝着后面搜索。

代码实现:

if (pHead == null || pHead.next == null)
{
    return pHead;
}
ListNode Head = new ListNode(0);
Head.next = pHead;
ListNode pre = Head;
ListNode last = Head.next;
while (last != null)
{
    if (last.next != null && last.val == last.next.val)
    {
        // 找到最后的一个相同节点
        while (last.next != null && last.val == last.next.val)
        {
            last = last.next;
        }
        pre.next = last.next;
        last = last.next;
    }
    else
    {
        pre = pre.next;
        last = last.next;
    }
}
return Head.next;

思路2:

递归

代码实现:

class Solution
{
    public:
        ListNode * deleteDuplication(ListNode * pHead)
        {
            if (pHead == NULL)
                return NULL;
            if (pHead != NULL && pHead - > next == NULL)
                return pHead;
            ListNode * current;
            if (pHead - > next - > val == pHead - > val)
            {
                current = pHead - > next - > next;
                while (current != NULL && current - > val == pHead - > val)
                    current = current - > next;
                return deleteDuplication(current);
            }
            else
            {
                current = pHead - > next;
                pHead - > next = deleteDuplication(current);
                return pHead;
            }
        }
};

思路3:(三个指针解决问题,思路清晰)

代码实现:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution
{
    public:
        ListNode * deleteDuplication(ListNode * pHead)
        {
            if (pHead == NULL || pHead - > next == NULL) return pHead;
            else
            {
                //新建一个节点,防止头结点要被删除
                ListNode * newHead = new ListNode(-1);
                newHead - > next = pHead;
                ListNode * pre = newHead;
                ListNode * p = pHead;
                ListNode * next = NULL;
                while (p != NULL && p - > next != NULL)
                {
                    next = p - > next;
                    if (p - > val == next - > val) //如果当前节点的值和下一个节点的值相等
                    {
                        while (next != NULL && next - > val == p - > val) //向后重复查找
                            next = next - > next;
                        pre - > next = next; //指针赋值,就相当于删除
                        p = next;
                    }
                    else //如果当前节点和下一个节点值不等,则向后移动一位
                    {
                        pre = p;
                        p = p - > next;
                    }
                }
                return newHead - > next; //返回头结点的下一个节点
            }
        }
};

以上就是关于删除链表中重复的结点的3种思路和代码实现了,想了解更多相关内容,请继续关注本站的Java实例专栏了解吧!