o2o商城上的二级网站,毕业设计做网站哪种好,网站模版自适应,南昌网站设计哪个最好链表是我们数据结构很重要的一点,也是常考的点
接下来我会先进行技巧总结,然后再通过具体的题来进行详解
总结
1.常用技巧 画图: 用笔是肯定比只用脑子强的,画图会更加清晰 引入虚拟头节点: 便于处理边界: 如果没有头节点,也就是第一个节点就有有效数据,就需要考虑边界问题…链表是我们数据结构很重要的一点,也是常考的点
接下来我会先进行技巧总结,然后再通过具体的题来进行详解
总结
1.常用技巧 画图: 用笔是肯定比只用脑子强的,画图会更加清晰 引入虚拟头节点: 便于处理边界: 如果没有头节点,也就是第一个节点就有有效数据,就需要考虑边界问题 方便对链表进行操作 大胆使用空间,定义变量: 一定不能让链表断开,一定要有节点指向后一节点 重点 使用快慢指针 判断链表是否有环 找链表中环的入口 倒数第 n 个节点
例子: 2.操作 创建一个新节点 头插 : 逆序列表 尾插 例题
2. 两数相加 这里的难点就是处理进位,只要将进位处理好就可以了
同时,这道题是逆序,如果是正序来进行计算的话,就需要先将链表转换为逆序再进行计算 代码:
这里的代码还可以进行优化,我只是按照分析的步骤完全模拟出来
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int t 0;//表示进位int number0;//表示当前节点的数ListNode newHead new ListNode();ListNode flag newHead;ListNode cur1 l1;ListNode cur2 l2;while (cur1!nullcur2!null){t cur1.valcur2.valt;number t%10;if(t10){t0;}else{t/10;}flag.next new ListNode(number);flagflag.next;cur1 cur1.next;cur2cur2.next;}//其中有一个为空while (cur1!null){t cur1.valt;number t%10;if(t10){t0;}else{t/10;}flag.next new ListNode(number);flagflag.next;cur1cur1.next;}while (cur2!null){t cur2.valt;number t%10;if(t10){t0;}else{t/10;}flag.next new ListNode(number);flagflag.next;cur2cur2.next;}//如果此时t还有数,就代表还要进位if(t!0){flag.next new ListNode(t);}return newHead.next;
}
一定要注意边界问题,及 当最后一个节点也需要进位的情况 24. 两两交换链表中的节点 这里我们也是需要构建一个虚拟头节点的,如果没有那么最开始两个节点和后续的节点的处理方式是不一样的,这样就需要分开处理,但是我们是可以统一处理的 代码:
public ListNode swapPairs(ListNode head) {if(headnull||head.nextnull){return head;}ListNode newNode new ListNode();newNode.nexthead;ListNode prev newNode;ListNode cur head;ListNode next cur.next;ListNode nnext next.next;while (cur!nullnext!null){cur.nextnnext;next.nextcur;prev.nextnext;//交换完成,向后移prevcur;curnnext;if(cur!null) nextcur.next;if(next!null) nnextnext.next;}return newNode.next;}
