关于链表的拓展基本操作-创新互联
一.通过X将链表排序;小的在前大的在后:
思考:遍历整个链表,与X作比较,小的尾插在SMALL里,大的尾插在BIG 里;遍历结束,判断SMALL或者BIG是否为空,如果是则只返回另一个的第一个结点,
class ListNode {
public int val;
public ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public ListNode(int val) {
this(val, null);
}
}
public class LinkedListInterview {
public ListNode separateByX(ListNode head, int x) {
ListNode sHead = null;
ListNode sEnd = null;
ListNode bHead = null;
ListNode bEnd = null;
for (ListNode cur = head; cur != null; cur = cur.next) {
if (cur.val < x) {
if (sHead == null) {
sHead = cur;
} else {
sEnd.next = cur;
}
sEnd = cur;
} else {//≥
if (bHead == null) {
bHead = cur;
} else {
bEnd.next = cur;
}
bEnd = cur;
}
}
if (sEnd == null) {
return bHead;
}
sEnd.next = bHead;
if (bEnd != null) {
bEnd.next = null;
}
return sHead;
}
private static ListNode createTestList() {
ListNode n1 = new ListNode(4);
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(2);
ListNode n4 = new ListNode(7);
ListNode n5 = new ListNode(6);
ListNode n6 = new ListNode(3);
ListNode n7 = new ListNode(8);
ListNode n8 = new ListNode(1);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
return n1;
}
// 三个重要节点
// 1. 咱创建的测试链表是不是出问题了?
// 2. 咱的分离程序是不是出问题了?
// 3. 咱的打印程序是不是出问题了?
private static void test() {
// 4 5 2 7 6 3 8 1
ListNode head = createTestList();
ListNode result = new LinkedListInterview().separateByX(head, 5);
// 4 2 3 1 5 7 6 8
for (ListNode cur = result; cur != null; cur = cur.next) {
System.out.println(cur.val);
}
}
public static void main(String[] args) {//主函数,调用test子函数
test();
}
}
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻标题:关于链表的拓展基本操作-创新互联
文章转载:http://myzitong.com/article/dcoijd.html