首页 > 代码库 > 面试题 - 无序单链表,排序

面试题 - 无序单链表,排序

有一个单链表,无序,给定一个值,将链表中小于这个值的节点放置于链表前面,节点之间相对顺序不变。

这个题目我是这样想的,我们遍历单链表,当遇到大于指定指的节点群后,再其后面查找小于指定值的节点群,然后交换两个节点群的位置。

思路有了,大致的代码:

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的节点群。

面试题 - 无序单链表,排序