锐客网

  1. 首页 > it技术 > >

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

目录

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

    前言 链表类型的习题常用的技巧就是定义指针来代替head的，替head走，要么就是数学问题，环形链表就是利用数学思想取解决的，要么就是定义双指针来操作链表。

    一、删除链表中给定值为key的节点
    定义两个变量，一个使待删除的节点，一个为待删除节点的前驱节点，最后记得判断头节点是否为要删除的节点，最后返回头节点。
    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
    【C++数据结构之链表详解】
    五、分割链表
    给定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 的部分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; }


    七、删除有序链表中重复节点
    双指针 遇到相等的就跳过 ，最后要将最后一个节点置为空。
    public ListNode deleteDuplicates(ListNode head) {if(head==null){return null; }ListNode prev=head; ListNode cur=head.next; while(cur!=null){if(prev.val==cur.val){cur=cur.next; }else{prev.next=cur; prev=cur; cur=cur.next; }}prev.next=cur; return head; }


    八、环形链表
    先用set判断是否存在 空间复杂度为O（N），不太符合题目要求
    public boolean hasCycle(ListNode head) {HashSet set=new HashSet<>(); while(head!=null){set.add(head); head=head.next; if(set.contains(head)){return true; }}return false; }

    2.快慢指针数学问题，快指针走两步，慢指针走一步，有环一定相遇，没有环就不会相遇 空间复杂度为O(1)
    public boolean hasCycle(ListNode head) {//快慢指针还是数学问题if(head==null||head.next==null){return false; }ListNode slow=head; ListNode fast=head.next; while(slow!=fast){if(fast==null||fast.next==null){return false; }fast=fast.next.next; slow=slow.next; }return true; }


    九、相交链表
    1.先利用set存储节点 之后循环判断，空间复杂度为O（N）时间复杂度为O（N），比较慢
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {HashSetset=new HashSet<>(); while(headA!=null){set.add(headA); headA=headA.next; }while(headB!=null){if(set.contains(headB)){return headB; }headB=headB.next; }return null; }

    2.双指针，确实没想出来，看了题解才知道是两个链表相连接，遍历是否有想交的节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode cur1=headA; ListNode cur2=headB; while(cur1!=cur2){cur1=cur1==null?headB:cur1.next; cur2=cur2==null?headA:cur2.next; }return cur1; }


    十、两数相加
    这道题没什么技巧，就是注意很多特殊情况，加完要判断进位，我第一次敲的时候能执行但是不能过，没有考虑到特殊情况。
    最后看评论解答就是用一个进位标志数来解决，学到了。
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode list=new ListNode(-1); ListNode head=list; int t=0; while(l1!=null||l2!=null||t!=0){if(l1!=null){t+=l1.val; l1=l1.next; }if(l2!=null){t+=l2.val; l2=l2.next; }list.next=new ListNode(t%10); list=list.next; t/=10; }return head.next; }


    十一、回文链表
    1.可以将链表中值存放在顺序表中，之后定义双指针遍历判断

    2.快慢指针带反转

    3.利用栈实现li
    public boolean isPalindrome(ListNode head) {//利用栈来实现回文结构Stack stack=new Stack<>(); ListNode cur=head; while(cur!=null){stack.push(cur.val); cur=cur.next; }ListNode cur1=head; while(cur1!=null){if(cur1.val!=stack.pop()){return false; }cur1=cur1.next; }return true; }

    定义快慢指针，之后反转链表来实现
    public boolean isPalindrome(ListNode head) {//快慢指针来反转链表if(head==null||head.next==null){return true; }ListNode fast=head; ListNode slow=head; while(fast.next!=null&&fast.next.next!=null){fast=fast.next.next; slow=slow.next; }//走到中间节点，反转链表slow=reverse(slow.next); while(slow!=null){if(head.val!=slow.val){return false; }head=head.next; slow=slow.next; }return true; }public ListNode reverse(ListNode 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; }

    C++数据结构之链表详解
    文章图片


    总结 本篇文章就到这里了，希望能给你带来帮助，也希望你能给多多关注脚本之家的更多内容！

      推荐阅读


      上一篇：MySql分页时使用limit+order|MySql分页时使用limit+order by会出现数据重复问题解决

      下一篇：基于@ComponentScan注解的使用详解