C++数据结构之链表详解

C++数据结构之链表详解,博智网带你了解详细信息。
目录

前言

一、删除链表中给定值为key的节点
二、反转链表
三、返回链表的中间节点
四、删除链表的倒数第K个节点
五、分割链表
六、合并两个有序链表
七、删除有序链表中重复节点
八、环形链表
九、相交链表
十、两数相加
十一、回文链表

总结

前言链表类型的习题常用的技巧就是定义指针来代替head的，替head走，要么就是数学问题，环形链表就是利用数学思想取解决的，要么就是定义双指针来操作链表。
一、删除链表中给定值为key的节点定义两个变量，一个使待删除的节点，一个为待删除节点的前驱节点，最后记得判断头节点是否为要删除的节点，最后返回头节点。
【C++数据结构之链表详解】 public ListNode removeElements(ListNode head, int val) {if(head==null){return null;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==val){prev.next=cur.next;}else{prev=cur;}cur=cur.next;}if(head.val==val){head=head.next;}return head;}
二、反转链表定义双指针法，类似于头插法，来将链表的节点头插法
cur节点是待反转的节点 curNext是保存下一个节点的地址值
1.先保存待反转节点下一个地址值，之后将头节点的next置空
2.只有用头插法将节点头插即可。
public ListNode reverseList(ListNode head) {//三指针法来反转链表if(head==null||head.next==null){return head;}ListNode cur=head;//要头插的节点ListNode curNext=head.next;//保存下一个节点的地址值cur=curNext;head.next=null;while(cur!=null){curNext=curNext.next;cur.next=head;head=cur;cur=curNext;}return head;}
三、返回链表的中间节点定义快慢指针，注意偶数节点和奇数节点的情况
注意判断条件在偶数情况下如果是判断fast.next.next就会空指针异常，必须把判断条件两个都加上。
public ListNode middleNode(ListNode head) {//定义快慢指针快指针比慢指针多走一步注意奇数和偶数情况if(head==null||head.next==null){return head;}ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}
四、删除链表的倒数第K个节点定义快慢指针快指针先走n-1步之后慢指针再走,修改地址值即可
public ListNode removeNthFromEnd(ListNode head, int n) {if(head==null){return null;}ListNode fast=head;ListNode dummy=new ListNode(0,head);ListNode slow=dummy;for(int i=1;i<n;i++){fast=fast.next;}while(fast.next!=null){fast=fast.next;slow=slow.next;}slow.next=slow.next.next;return dummy.next;}
五、分割链表给定X值，分割链表前面链表为小于X的值，后面链表为大于等于X的值
要考虑很多情况
1.第一次插入链表时要将头节点和尾巴节点都指向插入的节点
2.不是第一次插入时，只需要把尾巴节点next值指向插入的节点，之后把尾巴节点往后挪
3.如果前面链表为空，返回后面链表的头
4 。还需要将后面节点的next值置空，之后连接两个链表。
public ListNode partition(ListNode head, int x) {//分割链表将小于x的分为一部分，将大于等于x的分为一部分呢！乖乖yyif(head==null){return null;}ListNode xh=null;//小于x的头节点ListNode xe=null;;//小于x的尾巴节点ListNode Xh=null;//大于等于X的头节点ListNode Xe=null;//大于等于X的尾节点ListNode cur=head;while(cur!=null){if(cur.val<x){//小于X的部分if(xh==null){//第一次插入xh=cur;xe=cur;}else{//不是第一次插入xe.next=cur;xe=cur;}}else{//>=X 的部分if(Xh==null){//第一次插入Xh=cur;Xe=cur;}else{//不是第一次插入Xe.next=cur;Xe=cur;}}cur=cur.next;}//判断所有元素都大于x 前面的链表没有数据要返回后面的链表if(xh==null){return Xh;}xe.next=Xh;if(Xh!=null){//将最后一个元素置为nullXe.next=null;}return xh;}
六、合并两个有序链表和合并有序数组是一样的，链表复杂一些要将后面节点地址先保存，之后定义傀儡节点，按照值小的顺序连接起来
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {//1.思路就是先定傀儡节点，将链表穿起来定义两个变量将后面地址保存起来之后串糖葫芦一样串起来ListNode dummy=new ListNode(-1);ListNode head=dummy;//保存傀儡节点ListNode cur1=l1;//保存节点后面的地址值ListNode cur2=l2;while(l1!=null&&l2!=null){cur1=l1.next;cur2=l2.next;if(l1.val<=l2.val){dummy.next=l1;l1=cur1;}else{dummy.next=l2;l2=cur2;}dummy=dummy.next;}if(l1!=null){dummy.next=l1;}if(l2!=null){dummy.next=l2;}return head.next;}

C++数据结构之链表详解

推荐阅读