[LintCode] Insert Node in Sorted Linked List

littleGrow 发布于2019-08-15 13:24 / 2465人阅读

Problem

Insert a node in a sorted linked list.

Example

Given list = 1->4->6->8 and val = 5.

Return 1->4->5->6->8.

Solution

public class Solution {
    public ListNode insertNode(ListNode head, int val) {
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = new ListNode(val);
        
        //if val is the smallest in entire list
        if (head == null || val < head.val) {
            dummy.next = node;
            node.next = head;
            return dummy.next;
        }
        
        //while val is larger than head.val, loop the linked list and check the range between head & head.next to insert
        while (head != null && head.next != null) {
            if (head.val <= val && val <= head.next.val) {
                ListNode next = head.next;
                head.next = node;
                node.next = next;
                break;
            } else if (val > head.next.val) {
                head = head.next;
            }
        }
        
        //if node not inserted in the loop
        if (head.next == null) {
            head.next = node;
        }

        return dummy.next;
    }
}

云服务器服务器托管 linked LintCode Sorted LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68069.html

[LintCode] Insert into a Cyclic Sorted List

Problem Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node ...

Acceml 2019-08-15 13:27 评论0 收藏0
[LintCode] Remove Duplicates form Sorted List I &a

摘要：和上一道题不同的地方就是，需要用双指针操作，且最后要返回，以防止结点即的情况返回错误的结果。令，用进行查重操作，是的前结点。当和等值的时候，后移至第一个不等值的点，用指向新的即可。 Remove Duplicates form Sorted List I Problem Given a sorted linked list, delete all duplicates such tha...

int64 2019-08-14 15:29 评论0 收藏0
[LintCode/LeetCode] Merge Two Sorted Lists

摘要：先考虑和有无空集，有则返回另一个。新建链表，指针将和较小的放在链表顶端，然后向后遍历，直到或之一为空。再将非空的链表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...

dockerclub 2019-08-14 15:22 评论0 收藏0
[LeetCode] 708. Insert into a Cyclic Sorted List

Problem Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a r...

qpwoeiru96 2019-08-16 13:50 评论0 收藏0
[LintCode/LeetCode] Convert Sorted List to Balance

摘要：当链表为空时，中出现大于，返回。然后计算中点，以为界分别递归构建左右子树。顺序是，左子树根结点右子树。由于根节点是直接取构建，当前的已经被取用。所以在下一次递归构建右子树之前，要让指向。最后将和左右子树相连，返回。 Problem Given a singly linked list where elements are sorted in ascending order, conve...

Michael_Ding 2019-08-14 15:32 评论0 收藏0