1.针对链表的特性
(1)双指针的方法:因为不管是删除还是添加元素,都要涉及指定位置元素的上一个元素,因此需要设置前后两个指针来实现操作,同时针对题目特殊性也可能会有三指针的情况,如LeetCode82的去重,第一个指针作为删除操作的前一个指针,而后两个指针则用来查取重复范围
/**
*LeetCode 82
* 删除重复元素
*/
public ListNode deleteDuplicates(ListNode p) {
//特殊链表
if (p==null){
return null;
}
ListNode s=new ListNode(-1,p);
ListNode p1=s;
ListNode p2;
ListNode p3;
while ((p2=p1.next)!=null&&(p3=p2.next)!=null){
if (p2.val==p3.val){//元素的值相同
while ((p3=p3.next)!=null&&p3.val==p2.val){
}
//此时的p3为值不重复的元素---删除值重复元素
p1.next=p3;
}else{//元素的值不同---三个指针同时后移
p1=p1.next;
}
}
return s.next;
}
(2)递归:递归中可能存在多路递归的情况,是化多为少思想的应用,例如LeetCode23中,将合并多个链表的问题化简为二分递归和合并两个链表的情况,这种思想在解决数组内多个元素的处理时可能会用到
/**
* 合并多个升序链表
*/
public ListNode mergeKLists(ListNode[] lists) {
return spilt(lists, 0, lists.length - 1);
}
//采用二分的思想切割链表数组,化多为少,将数组切割为两两一组,然后合并后递归返回
private ListNode spilt(ListNode[] lists, int i, int j) {
if (lists.length == 0) { //---------------bug
return null;
}
if (i == j) {//---------------bug
return lists[i];
}
int m = (i + j) >>> 1;//二分切割 //---------------bug
ListNode left = spilt(lists, i, m);
ListNode right = spilt(lists, m + 1, j);
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(ListNode p1, ListNode p2) {
ListNode s = new ListNode(-1, null);//新链表的哨兵节点
ListNode p3 = s;
while (p2 != null && p1 != null) {
if (p1.val < p2.val) {//将p1接到新链表
p3.next = p1;
p1 = p1.next;
p3 = p3.next;
} else {
p3.next = p2;
p2 = p2.next;
p3 = p3.next;
}
}
if (p1 == null) {
p3.next = p2;
} else {
p3.next = p1;
}
return s.next;
}
2.特殊链表的考虑
针对算法输入的特殊链表,因为算法中访问到next元素的val时可能出现next为null而报空指针异常的错误,常见处理为p!=null && p.next != null,前者是链表为空的情况,后者是针对边界特殊情况的处理
3.哨兵节点
由于头结点的特殊性,主体逻辑会在边界处出现bug,引入哨兵节点则是为了将边界节点的处理也纳入主体逻辑中
--具体使用情况可能由处理的链表决定,待考察...
标签:p3,p1,ListNode,next,链表,算法,思考,null From: https://blog.csdn.net/fengdongnan/article/details/137178263