【重学数据结构篇2 下】链表代码练习

朴灿烈づ我的快乐病毒、 2022-10-13 00:27 106阅读 0赞

**一、准备工作**

> 为方便代码分享，便于有需要的朋友查看。我将练习代码放在了github上面，[传送门][Link 1]。  
> 关于GitHub：之前只知道GitHub可以去嫖别人优秀的代码，自己之前上传代码也是直接网站拖拽。在昨天看了软件工程关于团队合作之后，才发现控制版本的必要性，于是刚开始学习编程的同学，建议将非盈利的一些代码可以分享到github上面，也记录自己的提交和修改代码的过程。而版本控主要有CVS(收费最开始）、SVN、GIT（开源）。[git的使用][git]

IDEA进行配置集成git，也十分方面。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 1]

**二、代码练习**

**1. 基本操作**

链表的关键算法主要是`删除算法`、`插入算法`以及`逆置算法`，而其中逆置是最为常考（剑指Offer里面也出现不少），因此需要重点掌握其 `头插法`、`递归`与`迭代`、`栈`等办法解决逆置。

package nju.base.chapter2.base;
    
    import java.util.Scanner;
    
    /** * @AUTHOR LYF * @DATE 2021/7/4 * @VERSION 1.0 * @DESC * 链表基本操作 */
    public class LinkList { 
        ListNode head=new ListNode();
    
        // 头插法创建
        void createList(){ 
    
            Scanner scan =new Scanner(System.in);
            int val;
            while((val=scan.nextInt())!=-1){ 
                ListNode newNode = new ListNode(val,null);
                newNode.next = head.next;
                head.next = newNode;
            }
        }
    
        // 尾插入创建
        void creatListRail(){ 
            Scanner scan =new Scanner(System.in);
            int val;
            ListNode rail = head;// 需要.next进行连接起来,不能直接rail=head.next 再等于这样，因为为连接起来
            while((val=scan.nextInt())!=-1){ 
               rail.next = new ListNode(val,null);
               rail = rail.next;
            }
        }
    
    
        // 插入节点
    
        /** * 插入思路： * 先插入该节点的Next节点，在该点的next指向该节点 * @param val * @param pos */
        void insertNode(int val,int pos){ // 在第pos+1个节点之前加入
            //LinkNode p = head;
            ListNode p = head;
            int i=0;
            while(i!=pos&&p!=null)
                p=p.next;// 移动该位子
    
            ListNode newNode = new ListNode(val,null);
            newNode.next = p.next;
            p.next = newNode;
        }
        // 删除指定位置
        int removeIndexOf(int pos){ // 0对应第一个节点
            ListNode p = head;
            int i=0;
            while(i!=pos&&p!=null)
                p=p.next;// 移动该位子
            if(p.next==null)
                return -1;// 非法
            p.next = p.next.next;
            return 1;
        }
    
        // 删除指定元素(指针需要在被删元素的上一个才方便删除
        // 思路记录i确定位子调用removeIndexOf(),或者寻找next等于val
        int removeElementOf(int val){ 
            ListNode p = head;
            while(p.next!=null&&p.next.data!=val)
                p=p.next;
    
            if(p.next==null){ 
                //找不到
                return -1;
            }else{ 
                p.next=p.next.next;
                return 1;
            }
        }
    
        // 链表逆置（顺序表（数组）逆置，采用双指针）
        // 指针遍历+头插法 时间复杂度 O(n)
        // 单指针只是构造相同值？
        void reserve(){ 
            ListNode p=head.next;
            head.next = null;// 值空！！，末尾节点才能为空否则会接上原链表
            while(p!=null){ 
                ListNode newNode = new ListNode(p.data,null);
                newNode.next = head.next;
                head.next = newNode;
                p=p.next;//指针下移
            }
        }
    
        void reserve2(){ // 理解Java的引用
            ListNode p=head.next;
            while(p!=null){ 
                ListNode newNode = p;// 同一个？？会导致死循环，区别C++的指针概念
                p=p.next;//指针下移
                newNode.next = head.next;
                head.next = newNode;
            }
        }
    
        // 迭代逆置(将头节点也反转了）
        void reserve3(){ 
            ListNode cur = head.next;
            ListNode pre = null;
    
            while (cur!=null){ 
                ListNode tmp = cur.next;
                cur.next=pre;//逆置过来了
                pre = cur;
                cur = tmp;//进行迭代递进，依次向前移一个
            }
            ListNode newHead = new ListNode(0,null);
            newHead.next = pre;
            head = newHead;
        }
    
        //https://blog.csdn.net/a740169405/article/details/50682306?locationNum=9&fps=1
        ListNode reserve4(ListNode head1){ 
            if(head1==null||head1.next==null)
                return head1;
            else
            { 
                // 逆置除头结点外的链表
                ListNode rList = reserve4(head1.next);
                //
                head1.next.next = head1;
                head1.next=null;
                return rList;
            }
        }
    
        void outPut(ListNode list){ 
            ListNode p = list;
            while(p!=null){ 
                System.out.println(p.data);
                p=p.next;
            }
        }
    
        void outPut(){ 
            ListNode p = head.next;
            while(p!=null){ 
                System.out.println(p.data);
                p=p.next;
            }
        }
    }

**2. 剑指Offer相关练习**

[LeetCode 剑指Offer练习][LeetCode _Offer]

*  1.从尾到头打印链表
 *  2.O(1)时间删除链表节点
 *  3.求链表中倒数第K个节点
 *  4.反转链表
 *  5.合并两个有序链表
 *  6.复杂链表的复制
 *  7.二叉树转双向链表
 *  8.两个链表第一个公共节点
 *  9.链表中环的入口节点

（1）从尾到头打印链表

> 思路：其实就是逆置问题，十分简单; 采用栈或者ArrayList进行遍历链表存储 ，然后逆置存入数组即可。  
> 时间优化，可以先计算出长度，声明数组，然后遍历链表时存入数据。代码如下

public int[] reversePrint(ListNode head) { 
              ListNode p = head;
              Stack<Integer> stack = new Stack<>();
              while(p!=null){ 
                 stack.push(p.val);
                 p=p.next;
              }
              int[] arr = new int[stack.size()];
              int i=0;
              while(!stack.isEmpty()){ 
                 arr[i++]=stack.peek();
                 stack.pop();
              }
              return arr;
        }

public static int[] reversePrint(ListNode head) { 
            // 计算链表长度
            int len = getLength(head);
            // 创建一个长度为len的数组
            int[] ans = new int[len];
    
            for (int i = 0; i < len; i++) { 
                ans[len-i-1] = head.val;
                head = head.next;
            }
            return ans;
        }
    
        public static int getLength(ListNode head){ 
            int length = 0;
    
            while (head != null){ 
                length ++ ;
                head = head.next;
            }
    
            return length;
        }

（2）[删除链表节点][Link 2]

> 思路：寻找到删除节点，然后修改next指向即可。

public ListNode deleteNode(ListNode head, int val) { 
               if(head.val==val){ 
                   return head.next;
               }else{ 
                   ListNode p = head;
                   while(p.next!=null&&p.next.val!=val)
                      p=p.next;
    
                   p.next=p.next.next;
                   return head;   
               }
        }

> . O(1)时间删除链表节点 题目描述：给定单向链表的头指针和一个节点指针，在 O(1)时间复杂度内删除该 节点。  
> 思路：将要删除节点的下一个节点的值赋给要删除的节点，然后指向下下一个节 点代码实现：

public void deleteNode(ListNode head, ListNode deListNode) {  
        
        if (deListNode == null || head == null) 
                          return; 
       if (head == deListNode) {  
       head = null; } else {  // 若删除节点是末尾节点，往后移一个
      
      if (deListNode.nextNode == null) { 
        ListNode pointListNode = head; 
      while (pointListNode.nextNode.nextNode != null) {  
      pointListNode = pointListNode.nextNode; 
      }
      pointListNode.nextNode = null;
       } 
      else {  
      deListNode.data = deListNode.nextNode.data; 
      deListNode.nextNode = deListNode.nextNode.nextNode; 
      }
       }
        }

（3）求链表中倒数第K个节点

> 思路：  
> 法1：采用ArrayList存储节点，遍历一次即可，但是由于集合查询size()以及add()花费时间较多，时间复杂度只能达到超过19左右

List<ListNode> list=new  ArrayList<>();
          ListNode p = head;
          while(p!=null){ 
              list.add(p);
              p=p.next;
          }
          return list.get(list.size()-k);

> 法2：先计算链表长度，再次遍历找到该节点返回。（时间复杂度100%）

int len=0;
             ListNode p = head;
             while(p!=null){ 
                 len++;
                 p=p.next;
             }
    
             int i=0;
             p=head;
             while(i++<len-k){ 
                 p=p.next;
             }
             return p;

（4）[反转链表][Link 3]

> 头插法：  
> ![在这里插入图片描述][20210705171506835.png]

ListNode head1 = new ListNode(0);
            ListNode p = head;
            while(p!=null){ 
                ListNode tmp = new ListNode(p.val);
                tmp.next = head1.next;
                head1.next=tmp;
                p=p.next;
            }
            return head1.next;

> 迭代：迭代可能比较难理解，建议动手画一画（从第0,1，2这样小规模去推算，或者IDE调试也可以。）  
> ![在这里插入图片描述][20210705171800419.png]

// 法2，迭代
            ListNode cur =head;
            ListNode pre = null;
            while(cur!=null){ 
                ListNode tmp = cur.next;
                cur.next=pre;
                pre = cur;
                cur=tmp;
            }
            return pre;

(5) 有序链表合并

> 思路：比较判断，小的值优先插入，构造新的链表。  
> ![在这里插入图片描述][20210705172955745.png]

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
              ListNode c= new ListNode(0);
              ListNode p0=c;
              ListNode p1=l1,p2=l2;
              while(l1!=null||l2!=null){ 
                  if(l1!=null&&l2!=null)
                   { // 都非空，进行插入
                      if(l1.val<l2.val){ 
                         p0.next=new ListNode(l1.val);
                         l1=l1.next;
                      }else{ 
                         p0.next=new ListNode(l2.val);
                         l2=l2.next; 
                      }
                          p0=p0.next;
                   }else if(l1!=null){ 
                       p0.next =l1;
                       return c.next;
                   }else{ 
                       p0.next=l2;
                       return c.next;
                   }
              }
              return c.next;
        }

(6) 两个链表的第一个公共节点

> 思路，将其放在同一起点进行开始遍历，直到相同则返回。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
             // 思路都计算各自长度，从相同起点开始遍历。
             int lenA=getLen(headA),lenB=getLen(headB);
             ListNode p1=headA,p2=headB;
            if(lenA>lenB){ 
                    int i=0;
                    while(i++<lenA-lenB){ 
                        p1=p1.next;
                    }
             }else if(lenB>lenA){ 
                    int i=0;
                    while(i++<lenB-lenA){ 
                        p2=p2.next;
                    }
             }
    
                    while(p1!=p2){ 
                        p1=p1.next;
                        p2=p2.next;
                    }
                    return p1;
    
        }
        int getLen(ListNode list){ 
            int len =0;
            ListNode p = list;
            while(p!=null){ 
                p=p.next;
                len++;
            }
            return len;
        }

[Link 1]: https://github.com/lyf712/java-base/tree/master/java-base/src/main/java/nju/base/chapter2
[git]: https://www.runoob.com/git/git-install-setup.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70]: /images/20221005/4dd379fb5c5b4d6d9be5907f00415ffd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 1]: /images/20221005/ffcc5a7f667d48ea98db6282c64e1112.png
[LeetCode _Offer]: https://leetcode-cn.com/problem-list/xb9nqhhg/
[Link 2]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
[Link 3]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[20210705171506835.png]: /images/20221005/c3d937c719db43a097b01bca382b4906.png
[20210705171800419.png]: /images/20221005/29ca5451b75241a89f790980c71859a2.png
[20210705172955745.png]: /images/20221005/429b661e8efd4359ae9df2616f4dadb3.png