【数据结构高频知识点】java版

以你之姓@ 2022-09-03 12:23 113阅读 0赞

###  ###

*  链表
 *   *  反转链表：
     *  寻找链表中间节点
     *  寻找有环链表的入口

# 链表 #

## 反转链表： ##

递归法：（带头结点）

//用来反转整个链表
    public void reverse(){ 
    if(isEmpty()) return;
    reverse(head.next);
    
    public node reverse(node curr)
    { 
    if(curr.next == null)
    { 
    head.next = curr;
    return curr;/反转指定的节点，并返回反转后的节点
    }
    node pre = reverse(curr.next);
    pre.next = curr;//让返回的节点的下一个节点变为当前节点curr
    curr.next = null;/当前节点的下一个节点变为null
    return curr;
    }

迭代法：（无头结点）

static class ListNode{ 
    int val;
    ListNode next;
    public ListNode(int val,ListNode next)
    { 
    this.next = next;
    this.val = val;
    }
    public static ListNode iterate(ListNode head)
    { 
    ListNode pre = null,after;
    ListNode curr = head;//需要三个节点：当前节点 当前节点的下一个节点 当前节点的上一个节点
    while(curr != null)
    { 
    after = curr.next;
    curr.next = pre;
    pre = curr;
    curr = curr.next;//or curr = after
    }
    return pre;
    }

递归法：无头结点

public static ListNode recursion(ListNode head)
    { 
    if(head == null|| head.next == null) return head;
    ListNode newnode = recursion(head.next);
    newnode.next = head;
    head.next = null;
    return newnode;
    
    }

## 寻找链表中间节点 ##

//快慢指针法
    public String getnode(node<String>first)
    { 
    node<String> fast = first;
    node<String> slow = first;
    while(fast != null && fast->next != null)
    { 
    fast = fast.next.next;
    slow = slow.next;
    }
    return slow.item;
    }
    private static class node<T>//节点类
    { 
    T item;
    node next;
    public node(T item,node next)
    { 
    this.item = item;
    this.next = next;
    }
    }
    }

## 寻找有环链表的入口 ##

//修改上面的循环部分：
    public static node getEntrance(node<String>first){ 
    node<String> fast = first;
    node<String> slow = first;
    while(fast != null && fast.next != null)
    { 
    fast = fast.next.next;
    slow = slow.next;
    if(fast.equals(slow))
    { 
    node<String>temp = slow;
    break;//如果两个指针相遇
    }
    
    }
    while(temp!=null && temp != slow)
    { 
    temp = temp.next;
    slow = slow.next;
    if(temp.equals(slow))
    break;
    }
    return temp;
    }

判断链表是否有环：用快慢指针判断二者是否会相等，如果有相等则有环