Remove Duplicates from Sorted List 删除排序链表中的重复值节点

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
           if (head == null || head.next == null) return head;

            ListNode pHead = new ListNode(0);//输出链表
            ListNode pTail = pHead;//指向输出链表的最后一个节点
            ListNode p = head;//p用来遍历
            ListNode pNext = head.next;//pNext指向p的下一个节点

            while (p != null){
            if (pNext == null ) {//链表遍历完了,把最后的重复数的最后一个存入输出链表
                pTail.next = p;
                p = p.next;
                pTail = pTail.next;
                pTail.next = null;
                
            }
            else if (p.val == pNext.val){//p和pNext值相同则继续
                p = p.next;
                pNext = pNext.next;
            }else{   //p和pNext值不同,把p加入输出链表,p再指向下一个,pNext指向p的下一个
                pTail.next = p;
                p = p.next;
                pNext = pNext.next;
                pTail = pTail.next;
                pTail.next = null;
            }
        }
        return pHead.next;
    }
}


一次遍历,code by Tao2014

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;

        ListNode cur = head;
        while(cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            }
            else cur = cur.next;
        }
        return head;
    }
}

 

Tagged on: , , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.