本文共 1225 字,大约阅读时间需要 4 分钟。
题目:链表:现在有一个单链表。链表中每个节点保存一个整数,再给定一个值val,把所有等于val的节点删掉。给定一个单链表的头结点head,同时给定一个值val,请返回清除后的链表的头结点,保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。测试样例:
{1,2,3,4,3,2,1},2
{1,3,4,3,1}
思路:题目中已经保证了链表中一定有不等于val的其他值,因此删除后的链表不为null。
所谓删除结点pcur,需要保存pcur和前面的结点ppre,为了清楚还保留一个pnext(其实就是pcur.next),只要设置为ppre.next=pnext即刻。
本题中,遍历链表,时刻保持ppre,pcur,pnext如果某个结点需要删除就将ppre.next设置为pnext,然后ppre,pcur,ppnext均向下移动一个结点即可。特殊的:如果要删除的是头结点,那么可以采用在头结点之前加上一个dummy结点,dummy结点始终不会被删除,可以作为头结点,之后的结点删除与中间结点删除一样;对于尾结点的删除,此时pnext==null,直接将ppre.next设置为pnext(null)即可。因此除了使用一个dummy,其他没有什么特殊的。
技巧:这里通过在最前面加一个dummy作为头结点,使得原来的头结点head也向普通的结点一样可以用一样的逻辑进行删除。public class ClearValue { public ListNode clear(ListNode head, int val) {//题目已经保证了删除后链表不为null,显然head也不可能为null,可以不写一些特殊代码? ListNode dummy=new ListNode(-1); dummy.next=head; ListNode ppre=dummy; ListNode pcur=head; ListNode pnext=pcur.next; while(pcur!=null){//如果pcur要被删除,那么删除后将ppre的next指向pnext if(pcur.val==val){ ppre.next=pnext; }else{//如果pcur不需要被删除,那么接着向下遍历链表,移动ppre,pcur,pnext ppre=pcur; } pcur=pnext; if(pcur!=null){ pnext=pcur.next; } } return dummy.next; }}
转载地址:http://nvzin.baihongyu.com/