Linked List-查找链表的长度（迭代和递归）Find Length of a Linked List (Iterative and Recursive) （6）

柔情只为你懂 2023-09-24 19:58 33阅读 0赞

# 1.问题： #

![在这里插入图片描述][3901d1643bf44f018a7a5b217e6c3450.png]

> Input: 2->4->1->9->5->3->6  
> Output: 7

# 2.解决方法 #

## 1)查找链表长度的迭代方法： ##

### 解题思路 ###

1.  初始化计数为 0
2.  初始化一个节点指针，current = head。
3.  在 current 不为 NULL 时执行以下操作  
    当前 = 当前 -> 下一个  
    计数加 1。
4.  返回计数

public int getCount(){
        
           ListNode temp= head;
           int count=0;
           while(temp!=null){
        
               count++;
               temp=temp.next;
           }
           return count;
    }

`时间复杂度：O(N)`，其中N是链表的大小  
`辅助空间：O(1)`，因为使用了常量额外空间。

### 代码 ###

class LinkedList {
        
        static ListNode head;
        public static ListNode deleteNode(ListNode head){
        
            if (head == null)
                return null;
            // 将头指针移动到下一个节点
            ListNode temp = head;
            head = head.next;
    
            return head;
        }
        public int getCount(){
        
           ListNode temp= head;
           int count=0;
           while(temp!=null){
        
               count++;
               temp=temp.next;
           }
           return count;
         }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
            System.out.println("\n");
            System.out.println("Count of nodes is "
                    + list.getCount());
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

### 运行结果 ###

Created Linked list is:
    4 8 3 1 
    
    Count of nodes is 4

## 2)查找链表长度的递归方法： ##

### 解题思路 ###

1.  如果头部为 NULL，则返回 0。
2.  否则，返回 1 + getCount(head->next)  
    `时间复杂度：O(N)`，因为我们只遍历链表一次。  
    `空间复杂度: O(N)`，额外的空间用于递归调用栈。

public int getCount(ListNode node){
        
            if(node==null) return 0;
            return getCount(node.next)+1;
          }

### 代码 ###

package com.amy;
    
    
    import org.w3c.dom.ls.LSInput;
    
    import static java.util.Collections.sort;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
        static ListNode head;
        public static ListNode deleteNode(ListNode head){
        
            if (head == null)
                return null;
            // 将头指针移动到下一个节点
            ListNode temp = head;
            head = head.next;
    
            return head;
        }
          public int getCount(ListNode node){
        
            if(node==null) return 0;
            return getCount(node.next)+1;
          }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
            System.out.println("\n");
            System.out.println("Count of nodes is "
                    + list.getCount(head));
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

### 运行结果 ###

Created Linked list is:
    4 8 3 1 
    
    Count of nodes is 4

## 3）使用常量空间查找链表长度的递归方法： ##

`时间复杂度：O(N)`，因为我们只遍历列表一次。  
`辅助空间：O(1)`，由于我们使用的是尾递归函数，因此函数调用栈中没有使用额外的空间。

### 解题思路 ###

可以修改上面的递归方法，使其成为尾递归函数，这样我们的辅助空间将变为 O(1)

public int getCountRec(ListNode node,int count){
        /* 返回链表中节点的个数 */
            if(node==null) return count;
            return getCountRec(node.next,1+count);// 移动到下一个节点并增加计数
          }
        /* 包装 getCountRec() */
        public int getCount(){
        /* 返回链表中节点的个数 */
            return  getCountRec(head,0);// 移动到下一个节点并增加计数
        }

### 代码 ###

package com.amy;
    
    
    import org.w3c.dom.ls.LSInput;
    
    import static java.util.Collections.sort;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
        static ListNode head;
        public static ListNode deleteNode(ListNode head){
        
            if (head == null)
                return null;
            // 将头指针移动到下一个节点
            ListNode temp = head;
            head = head.next;
    
            return head;
        }
          public int getCountRec(ListNode node,int count){
        /* 返回链表中节点的个数 */
            if(node==null) return count;
            return getCountRec(node.next,1+count);// 移动到下一个节点并增加计数
          }
        /* 包装 getCountRec() */
        public int getCount(){
        /* 返回链表中节点的个数 */
            return  getCountRec(head,0);// 移动到下一个节点并增加计数
        }
    
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
            System.out.println("\n");
            System.out.println("Count of nodes is "
                    + list.getCount());
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

### 运行结果 ###

Created Linked list is:
    4 8 3 1 
    
    Count of nodes is 4

[3901d1643bf44f018a7a5b217e6c3450.png]: https://img-blog.csdnimg.cn/3901d1643bf44f018a7a5b217e6c3450.png