链表-真正的动态数据结构

创建节点

    public class Node {
        T val;
        Node next;

        public Node(T val, Node next) {
            this.val = val;
            this.next = next;
        }

        public Node() {
            this(null, null);
        }

        public Node(T val) {
            this(val, null);
        }
    } 

创建一个空链表

    //创建链表
    public Node header;
    private int size;

    public MyLinkedList() {
        this.header = null;
        this.size = 0;
    }

数据存储在节点中。
优点：不需要处理固态容量问题，可动态扩容。
缺点：丧失随机访问的能力。

添加元素

表头添加元素

    //表头添加元素
    public void addHead(T val) {
        Node cur = new Node(val, null);
        cur.next = header;
        header = cur;
        this.size++;
    }

表尾添加元素

    //表尾添加元素
    public void addTail(T val) {
        Node cur = new Node(val, null);
        Node p = header;
        while (p != null) {
            p = p.next;
        }
        p.next = cur;
        this.size++;
    }

表任意位置添加元素

    public void add(int index, T val) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is invalid!");
        }
        // 创建新结点
        Node node = new Node(val);
        // 1、先找pre
        //需要对头结点做特殊处理，原因是头结点没有pre(前驱结点)

        /* 添加虚拟头结点，保证链表中所有的结点都有pre*/
        Node dummyHeader = new Node(null, this.header);
        Node pre = dummyHeader;
        for (int i = 1; i <= index; i++) {
            pre = pre.next;
        }
        //2、、挂接
        node.next = pre.next;
        pre.next = node;
        //3、 更新头结点
        this.header = dummyHeader.next;
        // 3、更新size
        this.size++;
    } 

删除元素

    public void delete(int index)
    {
        if(index<0||index>this.size)return ;
        Node pre=this.header;
        int cnt=0;
        while(index!=cnt)
        {
            cnt++;
            pre=pre.next;
        }
        Node cur=pre.next;
        pre.next=cur.next;
        cur.next=null;
    }  

遍历链表

    @Override
    public String toString() {
        ArrayList<T> list = new ArrayList<>();
        Node cur = this.header;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        StringBuilder sb = new StringBuilder();
        for (T x : list) {
            sb.append(x + "--->");
        }
        sb.append("Null");
        return sb.toString();
    }

查询元素是否存在

    //查询元素在链表中是否存在
    public boolean contains(T val)
    {
        Node pre=this.header;
        while(pre!=null)
        {
            if(pre.val.equals(val))return true;
            else pre=pre.next;
        }
        return false;
    }  

力扣例题

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）

https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/

顺序查找

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode getKthFromEnd(ListNode head, int k) {
       ListNode pre=head,cur=head;
       int len=0;
       while(pre!=null)
       {
           len++;
           pre=pre.next;
       }
       int cnt=0;
       while(len-k!=cnt)
       {
           cnt++;
           cur=cur.next;
       }
       return cur;
   }
}

快慢指针

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

两两交换链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

创建虚拟头节点，疯狂迭代

/**
 * 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 swapPairs(ListNode head) {
        ListNode dummyhead=new ListNode(0);
        dummyhead.next=head;
        ListNode temp=dummyhead;
        while(temp.next!=null&&temp.next.next!=null)
        {
            ListNode node1=temp.next;
            ListNode node2=temp.next.next;
            node1.next=node2.next;
            node2.next=node1;
            temp.next=node2;
            temp=node1;
        }
        return dummyhead.next;
    }
}

递归（♂♂♂）

/**
 * 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 swapPairs(ListNode head) {
          if(head==null||head.next==null)return head;
          ListNode pre=head.next;
          head.next=swapPairs(pre.next);
          pre.next=head;
          return pre;
    }
}

反转链表 II - 力扣（LeetCode）

合并两个有序链表 - 力扣（LeetCode）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if(list1==null)return list2;
          if(list2==null)return list1;
          if(list1.val>list2.val)
          {
              list2.next=mergeTwoLists(list2.next,list1);
              return list2;
          }
          else
          {
              list1.next=mergeTwoLists(list1.next,list2);
              return list1;
          }
    }
}

反转链表 - 力扣（LeetCode）

/**
 * 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 reverseList(ListNode head) {
          ListNode pre=null;
          ListNode node=head;
          while (node!=null)
          {
              ListNode next=node.next;
              node.next=pre;
              pre=node;
              node=next;
          }
          return pre;
    }
}