首页 > 代码库 > [LintCode] 599 Insert into a Cyclic Sorted List 解题报告
[LintCode] 599 Insert into a Cyclic Sorted List 解题报告
Description
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 in the list. Return the inserted new node.
Notice
3->5->1 is a cyclic list, so 3 is next node of 1.
3->5->1 is same with 5->1->3
Example
Given a list, and insert a value 4:
3->5->1
Return 5->1->3->4
5/18/2017
算法班,未经验证
先找到list的头,再来循环找插入点。
1 public class Solution { 2 /** 3 * @param node a list node in the list 4 * @param x an integer 5 * @return the inserted new list node 6 */ 7 public ListNode insert(ListNode node, int x) { 8 // Write your code here 9 10 ListNode newNode = new ListNode(x); 11 if (node == null) { 12 newNode.next = newNode; 13 return newNode; 14 } else if (node.next == node) { 15 node.next = newNode; 16 newNode.next = node; 17 return node; 18 } 19 ListNode maxNode = node; 20 21 while (maxNode.next.val > maxNode.val) { 22 maxNode = maxNode.next; 23 } 24 if (maxNode.val < newNode.val || maxNode.next.val > newNode.val) { 25 newNode.next = maxNode.next; 26 maxNode.next = newNode; 27 return newNode; 28 } 29 30 ListNode node = maxNode.next; 31 while (node.next.val < newNode.val) { 32 node = node.next; 33 } 34 newNode.next = node.next; 35 node.next = newNode; 36 return newNode; 37 } 38 }
但是实际上可以在单纯遍历的时候找插入点
别人的答案
1 public class Solution { 2 /** 3 * @param node a list node in the list 4 * @param x an integer 5 * @return the inserted new list node 6 */ 7 public ListNode insert(ListNode node, int x) { 8 // Write your code here 9 10 if (node == null) { 11 node = new ListNode(x); 12 node.next = node; 13 return node; 14 } 15 16 ListNode head = node; 17 while (node != null && node.next != null) { 18 if (node.val < node.next.val) { 19 if (node.val <= x && x <= node.next.val) { 20 insertNode(node, x); 21 break; 22 } 23 } 24 else if (node.val > node.next.val) { 25 if (x > node.val || x < node.next.val) { 26 insertNode(node, x); 27 break; 28 } 29 } 30 else { // node.val == node.next.val 31 if (node.next == head) { 32 insertNode(node, x); 33 break; 34 } 35 } 36 node = node.next; 37 } 38 39 return head; 40 } 41 42 public void insertNode(ListNode node, int x) { 43 ListNode newNode = new ListNode(x); 44 newNode.next = node.next; 45 node.next = newNode; 46 } 47 }
[LintCode] 599 Insert into a Cyclic Sorted List 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。