帮你从算法的角度来认识链表------(二)

引言紧接上上文我们来分析一下链表的两个基础算法题练习203、206203.移除链表元素1要求给你一个链表的头节点head和一个整数val请你删除链表中所有满足Node.val val的节点并返回新的头节点。2示例3思路在遇到这种删除节点最终要返回新的头节点时我们一般要设置一个哨兵节点简单来说就是定位一下头节点如果不设置的话直接按照题中给出的头节点来进行遍历那么我们最终遍历完这个头结点也不会回到原来的起点因为单向链表不能往前走另外再设置一个指针用来遍历整个链表这个时候就疑惑了设置哨兵节点是为了定位头结点的位置那为什么还有设置一个指针呢如果直接用题目中给出的head来进行遍历这样会导致想要删除头节点删除不了失去了能修改链表的前驱节点因为删除节点需要前驱节点来进行删除(pre.nextpre.next.next因此我们要设置一个哨兵节点和一个指针来帮助我们完成删除指定节点一系列的题4代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummynew ListNode(0,head); ListNode curdummy; while(cur.next!null){ if(cur.next.valval){ cur.nextcur.next.next; }else{ curcur.next; } } return dummy.next; } }206.反转链表1要求给你单链表的头节点head请你反转链表并返回反转后的链表。2示例3思路1(头插法)就是把一个节点node指向链表头节点node.next更新为链表的头节点那么node就插在了链表的左侧新链表的头节点为node新插入的节点一直为新链表的头节点因此叫头插法举个例子对于链表 4→2→6结合代码来说顺序为第一次插入得到链表4第二次插入得到链表2-4第三次插入得到链表6-2-44代码1class Solution { public ListNode reverseList(ListNode head) { ListNode pre null; ListNode cur head; while (cur ! null) { ListNode nxt cur.next; cur.next pre; pre cur; cur nxt; } return pre; } }5思路2尾插法递归先递不断调用自身函数找到原链表的尾节点再归依次把节点插入到尾部因为我们是从原链表的尾部向前归因此依次把节点插到新链表的尾部即可实现反转6代码2class Solution { public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; // 链表末尾即下面的 revHead } ListNode revHead reverseList(head.next); // 递一直到链表末尾 ListNode tail head.next; // 归head.next 就是新链表的末尾 tail.next head; // 把 head 插在新链表的末尾 head.next null; return revHead; } }