Java-数据结构-链表＜一＞_java 链表

一. 链表简单介绍 

        链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）[1]，通常链表的头被称为head，尾部一般用null表示。【图自[1]】

        链表的类型有单链表，双链表，循环链表等。数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。

二. 链表的代码实现

leetcode中对单向链表的典型实现

  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; }
  }

三. leetcode&牛客实例

1. leetcode206 && nowcoderBM1 反转链表

        给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

（1）数组（list）方法：全部将值取出再重新赋值 

class Solution {
    public ListNode reverseList(ListNode head) {
        //1.全部取值重新赋值
        return reverseList1(head);
    }
    public ListNode reverseList1(ListNode head){
        if(head == null) return null;
        LinkedList<Integer> list = new LinkedList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        ListNode new_head = new ListNode(list.removeLast());
        ListNode cur = new_head;
        ListNode temp;
        while(!list.isEmpty()){
            temp = new ListNode(list.removeLast());
            cur.next = temp;
            cur = temp;
        }
        return new_head;
    }
}

（2）原地反转

        原地反转需要三个指针，三个指针在这里分别定义为tail,middle,pre。

class Solution {
    public ListNode reverseList(ListNode head) {
        //2.原地反转
        return reverseList2(head);
    }
    
    public ListNode reverseList2(ListNode head){
        if(head == null) return null;
        ListNode tail = head;
        if(tail.next == null) return tail;
        ListNode middle = head.next;
        ListNode pre = middle.next;
        tail.next = null;