题解 | #链表分割#
链表分割
http://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
1.new 两个新链表用来进行关于x的划分，以及相对位置不变；
2.遍历给定链表，进行划分；
注意：
（1）如何进行结点插入/新链表合并 ？---因为尾插效率低，所以我们使用标记，随着插入进行标记，而合并也会因为标记变得更简单
（2）如何设置标记？---首先我们分别对两个新链表设置标记变量，但由于空链表指向next是非法的，所以我们一开始会在两个新链表中各加入一个结点
（3）注意合并时候要忽略无意义结点(一开始的结点)，以及注意第2个链表的最后一个结点要指向空
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if(pHead==null){
return pHead;
}
//1.先new两个链表，方便后续使用
ListNode head1 = new ListNode(0); //保证链表1不为空--可以指向next
ListNode head2 = new ListNode(0); //保证链表2不为空--可以指向next
ListNode flag1 = head1; //一开始标记链表一的头结点
ListNode flag2 = head2; //一开始标记链表二的头结点
//2.判断给定链表中的结点val与x之间的关系
ListNode cur = pHead;
while(cur!=null){
if(cur.val < x){
flag1.next=cur;
flag1=flag1.next;
}else{
flag2.next=cur;
flag2=flag2.next;
}
cur=cur.next;
}
//3.开始进行善后及合并两个新链表
//3.1.善后
flag2.next=null; //把链表2最后一个结点的next置空，防止出现与其他结点相连的状况
//3.2.合并两个新链表
flag1.next=head2.next; //注意把一开始的无意义结点剔除
return head1.next;
}
}
查看13道真题和解析