链表常用技巧和操作总结

链表是我们数据结构很重要的一点,也是常考的点

接下来我会先进行技巧总结,然后再通过具体的题来进行详解

总结

1.常用技巧

• 画图: 用笔是肯定比只用脑子强的,画图会更加清晰

• 引入虚拟头节点:

  • 便于处理边界: 如果没有头节点,也就是第一个节点就有有效数据,就需要考虑边界问题

  • 方便对链表进行操作

• 大胆使用空间,定义变量: 一定不能让链表断开,一定要有节点指向后一节点

•  重点 使用快慢指针

  • 判断链表是否有环

  • 找链表中环的入口

  • 倒数第 n 个节点

例子:

2.操作

• 创建一个新节点

• 头插 : 逆序列表

• 尾插

例题

2. 两数相加

这里的难点就是处理进位,只要将进位处理好就可以了

同时,这道题是逆序,如果是正序来进行计算的话,就需要先将链表转换为逆序再进行计算

代码:

这里的代码还可以进行优化,我只是按照分析的步骤完全模拟出来

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int t = 0;//表示进位int number=0;//表示当前节点的数ListNode newHead = new ListNode();ListNode flag = newHead;ListNode cur1 = l1;ListNode cur2 = l2;while (cur1!=null&&cur2!=null){t = cur1.val+cur2.val+t;number= t%10;if(t<10){t=0;}else{t/=10;}flag.next= new ListNode(number);flag=flag.next;cur1 = cur1.next;cur2=cur2.next;}//其中有一个为空while (cur1!=null){t = cur1.val+t;number= t%10;if(t<10){t=0;}else{t/=10;}flag.next= new ListNode(number);flag=flag.next;cur1=cur1.next;}while (cur2!=null){t = cur2.val+t;number= t%10;if(t<10){t=0;}else{t/=10;}flag.next= new ListNode(number);flag=flag.next;cur2=cur2.next;}//如果此时t还有数,就代表还要进位if(t!=0){flag.next= new ListNode(t);}return newHead.next;
}

一定要注意边界问题,及 当最后一个节点也需要进位的情况 

24. 两两交换链表中的节点

这里我们也是需要构建一个虚拟头节点的,如果没有那么最开始两个节点和后续的节点的处理方式是不一样的,这样就需要分开处理,但是我们是可以统一处理的

代码:

public ListNode swapPairs(ListNode head) {if(head==null||head.next==null){return head;}ListNode newNode = new ListNode();newNode.next=head;ListNode prev = newNode;ListNode cur = head;ListNode next = cur.next;ListNode nnext = next.next;while (cur!=null&&next!=null){cur.next=nnext;next.next=cur;prev.next=next;//交换完成,向后移prev=cur;cur=nnext;if(cur!=null) next=cur.next;if(next!=null) nnext=next.next;}return newNode.next;}