首页 > 代码库 > 面试题 - 无序单链表，排序
面试题 - 无序单链表，排序
有一个单链表，无序，给定一个值，将链表中小于这个值的节点放置于链表前面，节点之间相对顺序不变。
这个题目我是这样想的，我们遍历单链表，当遇到大于指定指的节点群后，再其后面查找小于指定值的节点群，然后交换两个节点群的位置。
思路有了，大致的代码：
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个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。