首页 > 代码库 > 面试题 - 无序单链表,排序
面试题 - 无序单链表,排序
有一个单链表,无序,给定一个值,将链表中小于这个值的节点放置于链表前面,节点之间相对顺序不变。
这个题目我是这样想的,我们遍历单链表,当遇到大于指定指的节点群后,再其后面查找小于指定值的节点群,然后交换两个节点群的位置。
思路有了,大致的代码:
function LinkNode(data){ this.data = http://www.mamicode.com/data;"LinkList: " + ret.join(" -> "); }}function test(list, v){ var n1,n2,n3,n4,n5,cur; cur=list.head; while(cur != null){ if(cur.data>=v){ n2 = cur; n3 = cur; while(n3.next != null && n3.next.data >= v){ n3 = n3.next; } n4 = n3.next; n5 = n3.next; while(n5!=null && n5.next != null && n5.next.data < v){ n5 = n5.next; } if(n4 == null){ return; } // if(n1 == null){ list.head = n4; }else{ n1.next = n4; } var c = n5.next; n5.next = n2; n3.next = c; cur = n4; } n1 = cur; cur = cur.next; }}var a = new LinkList(3);a.insert(8);a.insert(7);a.insert(6);a.insert(5);a.insert(4);a.insert(9);a.insert(3);a.insert(2);a.insert(7);a.insert(1);console.log(a.toString());test(a, 5);console.log(a.toString());
运行效果:
我上面的代码简化一个地方,将等于value的节点也规划成大于value的节前群中,这样单链表中只会存在两种类型的节点,大于和小于,因此上面代码中,n3之后肯定是n4,如果需要将等于独立出来,那么我们就再需要两个变量来记录等于value的节点群。
面试题 - 无序单链表,排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。