day10

83. 删除排序链表中的重复元素

简单

1.1K

相关企业

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode p=head;
        ListNode q=p.next;
        while(q != null){
            if(p.val == q.val){
                p.next = q.next;
                q=q.next;
            }else{
                p=p.next;
                q=q.next;
            }
        }
        return head;
    }
}

82. 删除排序链表中的重复元素 II

中等

1.2K

相关企业

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;
 
        ListNode pre_head = new ListNode();
        pre_head.next = head;
        ListNode pre = pre_head;
        ListNode cur = pre.next;
 
        while(cur != null && cur.next != null){
            if(cur.val == cur.next.val){
                while(cur != null && cur.next != null && cur.val == cur.next.val){
                    cur=cur.next;
                }
                pre.next = cur.next;
                cur = pre.next;
            }else{
                pre = pre.next;
                cur = cur.next;
            }
        }
        return pre_head.next;
    }
}

234. 回文链表

简单

1.8K

相关企业

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
//  */
// class Solution {
//     public boolean isPalindrome(ListNode head) {
//         // ArrayList a = new ArrayList();
//         // while(head != null){
//         //     a.add(head.val);
//         //     head=head.next;
//         // }
//         // int l=0;
//         // int r=a.size()-1;
//         // while(l<=r && a.get(l) == a.get(r)){
//         //     l++;r--;
//         // }
//         // if(l<=r)
//         //     return false;
//         // else 
//         //     return true;
 
//     }
// }
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
 
        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);
 
        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        
 
        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }
 
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
 
    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

148. 排序链表

中等

2.1K

相关企业

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        ArrayList<Integer> list = new ArrayList();
        ListNode p =head;
 
        while(head != null){
            list.add(head.val);
            head = head.next;
            p = null;
            p=head;
        }
        head = new ListNode();
        Collections.sort(list);
        p=head;
        int n = list.size();
        for(int i =0;i<n;i++){
            ListNode q = new ListNode(list.get(i));
            p.next = q;
            p=p.next;
        }
        return head.next;
    }
}