LintCode: Insert Node in Sorted Linked List

Insert Node in Sorted Linked List



Similar Problems:


Description
Insert a node in a sorted linked list.

Example

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

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

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/insert-node-in-sorted-linked-list
// Basic Ideas:
// Complexity: Time O(n), Space O(1)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

/**
 * @param head: The head of linked list.
 * @param val: An integer.
 * @return: The head of new linked list.
 */
func insertNode (head *ListNode, val int) *ListNode {
    // write your code here
    dummyNode := &ListNode{0, head}
    newNode := &ListNode{val, nil}
    p := dummyNode
    for p.Next != nil && p.Next.Val < val {
        p = p.Next
    }
    p.Next, newNode.Next = newNode, p.Next
    return dummyNode.Next
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.