1.链表的引入

由于在ArrayList任意位置插入或者删除元素时就需要将元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合在任意位置插入或者删除元素,因此引入了LinkedList,即链表结构。

2.链表的分类

2.1 单向或者双向

无头指每一个节点都可以存放数字

 2.2 带头或者不带头

2.3 循环或者非循环

无头单向非循环结构简单,作为其他数据结构的子结构,在笔试面试中出现的比较多

 同时,无头双向循环链表,为LinkedList底层实现的链表。

3.链表的实现(无头单项非循环)

import java.util.LinkedList;

public class MyLinkedList implements IList{
    static class ListNode {
        public int val;
        public ListNode preV;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

    }
    public ListNode head;//这里的head并不是指头而是方便取的名字
    public ListNode last;
    @Override
    public void addFirst(int data) {
       ListNode cur = head;
       ListNode node = new ListNode(data);
       if(head.next == null){
           head = last = node;
       }else{
           node.next = cur;
           cur.preV = node;
           head = node;
       }
    }

    @Override
    public void addLast(int data) {
        ListNode cur = head;
        ListNode node = new ListNode(data);
        if(head == null) {
            head = last = node;
        }else{
            last.next = node;
            node.preV = last;
            last = node;
        }

        }

    @Override
    //在指定位置增删元素
    public void addIndex(int index, int data) {
        int len = size();
        if(index < 0 || index > len ){
            System.out.println("不符合条件");
            return;
        }if(index == 0){
            addFirst(index);
            return;
        }if(index == len){
            addLast(data);
            return;
        }else{
            ListNode cur = findOfKey(index);
            ListNode node = new ListNode(data);
            node.next = cur;
           node.preV = cur.preV;
            cur.preV.next = node;
           cur.preV = node;
        }

    }
    private ListNode findOfKey(int index){
        ListNode cur = head;
        while(index != 0){
           cur = cur.next;
           index--;
        }
        return cur;
    }


    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key)
            {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
       ListNode cur = head;
       while(cur != null) {
           if (cur.val == key) {
               if (cur == head) {
                   head = head.next;
                   if (head != null) {
                       head.preV = null;
                   }
               } else {
                   cur.preV.next = cur.next;
                   if ( cur.next == null) {
                       last = last.preV;
                   }else {
                       cur.next.preV = cur.preV;
                   }
               }
           }
           cur =cur.next;
       }
    }

    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.preV = null;
                    }
                }
            else {
                    cur.preV.next = cur.next;
                    if (cur.next == null) {
                        last = last.preV;
                    }
                    cur.next.preV = cur.preV;
                }
            }
            cur = cur.next;
        }

    }



    @Override
    public int size() {
        ListNode cur = head;
        int len = 0;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        return len;
    }

    @Override
    public void clear() {
        ListNode cur = head;
        if(cur != null){
            ListNode curN = cur.next;
            cur.preV = null;
            cur.next = null;
            cur = curN;
        }
        head = null;
        last = null;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

接口: 

public interface IList {

     public void addFirst(int data);

     public void addLast(int data);

     public void addIndex(int index,int data);

     public boolean contains (int key);

     public void remove(int key);

     public void removeAllKey(int key);

     public int size();
     public void clear();
     public void display();


}

4.链表面试题

4.1 移除链表元素

 public class Solution {
  
        public ListNode removeElements(ListNode head, int val) {
            if(head == null){
                return head;
            }
            ListNode pre = head;
            ListNode cur = head.next;
            while(cur != null){
                if(cur.val == val){
                    pre.next = cur.next;
                    cur = cur.next;
                }else{
                    pre = cur;
                    cur = cur.next;
                }
            }
            if(head.val == val){
                head = head.next;
            }
            return head;
        }
    }

 4.2 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
       return head;
    }
}

4.3 链表的中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
    return slow;

    }
}

4.4 返回倒数第k个节点

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        if(head == null){
            return head.val;
        }
        ListNode fast = head;
        ListNode slow = head;
        int count = k - 1;
        while(count != 0){
            fast = fast.next;
            count--;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

 4.5 合并两个有序链表

 /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
         ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
       while(list1 != null && list2 != null){
          if(list1.val <= list2.val){
              tmp.next = list1;
              list1 = list1.next;
              tmp = tmp.next;
          }else{
              tmp.next = list2;
              tmp = tmp.next;
              list2 = list2.next;
          }
      }
       if(list1 != null){
           tmp.next = list1;
       }
       if(list2 != null){
           tmp.next = list2;
       }
       return newHead.next;
    }
}

 4.6 链表分割

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
         ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = pHead;
        while(cur != null){
            if(cur.val < x){
                if(as == null){
                    as = ae = cur;
                }else{
                      ae.next = cur;
                      ae = ae.next;
                }
            }else{
                if(bs == null){
                     bs = be =cur;
                }else{
                     be.next = cur;
                     be = be.next;
                }
            }
            cur = cur.next;
        }
        if(as == null){
            return bs;
        }
         ae.next = bs;
        if(bs != null){
            be.next = null;
        }
            return as;
    }
    }

 4.7 链表回文

 

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A == null){
            return false;
        }
        // write code here
      ListNode fast = A;
      ListNode slow = A;
      while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
      }
       ListNode cur = slow.next;
     while(cur !=  null){
         ListNode curN = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curN;
     }
    while(A != slow){
        if(A.val != slow.val){
            return false;
        }
        if(A.next == slow){
            return true;
        }
        A= A.next;
        slow = slow.next;
    }
    return true;
    }
}

4.8 相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode pl = headA;
       ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        //计算长度
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        while(ps != null){
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        //计算两个链表的差值
        int len = lenA - lenB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        while(len != 0){
            pl = pl.next;
            len--;
        }
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null){
            return null;
        }
        return pl;
    }
}

 4.9 环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast  ==  slow ){
                return true;
            }
        }
        return false;
    
    }
}

 5.双向链表的基本实现(LinkedList)

public class MyLinkedList implements IList{
    static class ListNode {
        public int val;
        public ListNode preV;
        public ListNode next;
 
        public ListNode(int val) {
            this.val = val;
        }
 
    }
    public ListNode head;
    public ListNode last;
    @Override
    public void addFirst(int data) {
       ListNode cur = head;
       ListNode node = new ListNode(data);
       if(head.next == null){
           head = last = node;
       }else{
           node.next = cur;
           cur.preV = node;
           head = node;
       }
    }
 
    @Override
    public void addLast(int data) {
        ListNode cur = head;
        ListNode node = new ListNode(data);
        if(head == null) {
            head = last = node;
        }else{
            last.next = node;
            node.preV = last;
            last = node;
        }
 
        }
 
    @Override
    //在指点位置增删元素
    public void addIndex(int index, int data) {
        int len = size();
        if(index < 0 || index > len ){
            System.out.println("不符合条件");
            return;
        }if(index == 0){
            addFirst(index);
            return;
        }if(index == len){
            addLast(data);
            return;
        }else{
            ListNode cur = findOfKey(index);
            ListNode node = new ListNode(data);
            node.next = cur;
           node.preV = cur.preV;
            cur.preV.next = node;
           cur.preV = node;
        }
 
    }
    private ListNode findOfKey(int index){
        ListNode cur = head;
        while(index != 0){
           cur = cur.next;
           index--;
        }
        return cur;
    }
 
 
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key)
            {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
 
    @Override
    public void remove(int key) {
       ListNode cur = head;
       while(cur != null) {
           if (cur.val == key) {
               if (cur == head) {
                   head = head.next;
                   if (head != null) {
                       head.preV = null;
                   }
               } else {
                   cur.preV.next = cur.next;
                   if ( cur.next == null) {
                       last = last.preV;
                   }else {
                       cur.next.preV = cur.preV;
                   }
               }
           }
           cur =cur.next;
       }
    }
 
    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.preV = null;
                    }
                }
            else {
                    cur.preV.next = cur.next;
                    if (cur.next == null) {
                        last = last.preV;
                    }
                    cur.next.preV = cur.preV;
                }
            }
            cur = cur.next;
        }
 
    }
 
 
 
    @Override
    public int size() {
        ListNode cur = head;
        int len = 0;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        return len;
    }
 
    @Override
    public void clear() {
        ListNode cur = head;
        if(cur != null){
            ListNode curN = cur.next;
            cur.preV = null;
            cur.next = null;
            cur = curN;
        }
        head = null;
        last = null;
    }
 
    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //在指定位置进行打印
    public void display2(ListNode newHead) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
 
        public ListNode reverseList() {
            if(head == null){
                return head;
            }
            ListNode cur = head.next;
            head.next = null;
            while(cur != null){
                ListNode curN = cur.next;
                cur.next = head;
                head = cur;
                cur = curN;
            }
            return head;
        }
 
    
    }

5.1LinkedList的一些性质

 5.2 LinkedList的使用

 2 其他方法的使用

 

3 LinkedList的遍历

6.ArrayList 与 LinkedList的区别

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部