刷Leecode笔记（二）链表篇

链表篇

移除链表元素，设计链表，反转链表，交换链表节点，删除链表，相交链表，环形链表

链表

链表这一张，集合中的LinkedList底层实现就是双链表，封装好了增删改查等各种方法，这里相当于是手写源码了属于是

203.移除链表元素

/**
 * 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 removeElements(ListNode head, int val) {
        //传入头结点和值，头结点是一个结构体，包含一个值，和下一个节点
        //next，以及三个构造器
        ListNode preNode = new ListNode(0);
        preNode.next = head;
        ListNode temp = preNode;//定义临时表示当前节点
        while(temp.next != null){
            if(temp.next.val == val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next;
            }
        }
        return preNode.next;

    }
}
//手写源码了属于是，定义一个虚拟头结点，确保不用在判断头结点就是要删除的情况，
//其次就是，定义零食变量temp的节点，表示当前结点，以便后续操作

707.设计链表

他奶奶的，人linkedList底层封装好的，要我重新设计，写这些方法，离谱啊，算了，熟能生巧

//定义链表类，val是当前节点的值，next是指向下一个节点的引用
class ListNode {
    int val;
    ListNode next;

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

class MyLinkedList {
    int size; // 链表的长度
    ListNode head;// 链表的首节点

    // 初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    // 获取下标为index节点的数值，如果下标无效，则返回-1
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode preNode = head;
        for (int i = 0; i <= index; i++) {
            preNode = preNode.next;
        }
        return preNode.val;
    }

    // 将一个值为val的节点差插入到链表第一个元素之前
    public void addAtHead(int val) {

        addAtIndex(0, val);
        // ListNode Node = new ListNode(val);
        // Node.next = head.next;
        // head.next = Node;
        // size++;
    }

    // 将一个值val的节点加入到链表作为链表的最后一个元素
    public void addAtTail(int val) {
        addAtIndex(size, val);
        // ListNode Node = head;
        // for (int i = 0; i < size; i++) {
        // Node = Node.next;
        // }
        // Node.next = new ListNode(val);
        // size++;
    }

    // 将值为val的节点插入到index节点之前，若index==链表长度，插入最后
    // 若大于链表长度，则不会插入
    public void addAtIndex(int index, int val) {
        if (index > size || index < 0) {
            return;
        }

        ListNode temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        ListNode Node = new ListNode(val);
        Node.next = temp.next;
        temp.next = Node;
        size++;
    }

    // 如果下标有效，则删除这个节点
    public void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }
        ListNode temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
        size--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
  /*单链表的具体实现思路是有的，定义，创建，初始化的各种细节都需要熟悉
  不需要定义head头结点之前的虚拟节点，妈的，自动有了，get方法写错，排查了半天，浪费时间
  第二遍重写花了16分钟，还有小瑕疵。边界条件index的判断

206.反转链表

/**
 * 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 n = head;
        ListNode p = null;
        ListNode t = null;
        while (n != null) {
            t = n.next;// 先保存这个节点,不然反转后会丢失
            n.next = p;
            p = n;// n和p都向后一位
            n = t;
        }
        return p;// 最后一次n被赋值为null，返回p作为头结点
    }
}
//单链表无法返回找回，需要临时变量存储下一个节点的位置

24.两两交换链表中的节点

/**
 * 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 pre = new ListNode(0);
        pre.next = head;
        ListNode n = pre;
        ListNode t;
        ListNode firstNode;
        ListNode secondNode;
        while (n.next != null && n.next.next != null) {
            t = n.next.next.next;
            firstNode = n.next;
            secondNode = n.next.next;

            n.next = secondNode;
            secondNode.next = firstNode;
            firstNode.next = t;
            n = firstNode;
        }
        return pre.next;
    }
}
/*交换的方法画个图就出来了，三步走，要记录的临时变量太多了，开始写那么多的next的头都写晕了
然后，因为临时变量要不停的变，要在循环内赋值，不能在循环外面赋值
然后，&& 与&的问题，开始写的是，n.next.next != null && n.next != null，运行错误
& 是两个条件都要判定一下，而&&是第一个不正确就不判断第二个了，当然next都=null了，就更不需要判断后面的了，所以要把小的放在&&的前面

19.删除链表倒数第n个节点

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode first = pre;
        ListNode last = pre;
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            last = last.next;
        }
        last.next = last.next.next;
        return pre.next;
    }
}
/*很巧妙的方法，删除简单，关键是找到链表还是倒数第n个元素，众所周知，链表不好查询
双指针定义了一个长度为n的区间，不停移动 ，直到快指针指向null，慢指针的位置后面就是要删除元素的位置

160.相交链表

/*末尾对齐，指针B多移动(lenB-lenA),然后一起向后遍历是否相等
	需要注意的是，要判断长度，
	*/

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        int lenA = 0;
        int lenB = 0;
        while (A != null) {
            lenA++;
            A = A.next;
        }
        while (B != null) {
            lenB++;
            B = B.next;
        }
        A = headA;// 刚刚遍历长度到末尾了，再指向头结点
        B = headB;
        if (lenA > lenB) {// 交换A，B头结点,确保A短
            int t = lenA;
            lenA = lenB;
            lenB = t;

            ListNode T = A;
            A = B;
            B = T;
        }
        int d = lenB - lenA;
        while (d-- > 0) {
            B = B.next;
        }
        while (A != null) {
            if (A == B) {
                return A;
            }
            A = A.next;
            B = B.next;
        }
        return null;
    }
}

142.环形链表

/*定义两个指针，fast，slow，指向链表的head，，fast指针每次走两步，slow指针每次走一步
	1：fast指针走到null，说明链表无环，
	2.若有环的话，fast一定会遇到slow，{
		1.fast先进环，会在环内转圈圈，slow再进环，会在环内相遇
		2.假定一个环，fast在任意节点追赶slow指针，无论环数为奇数偶数，初始差多少，这样理解，等同于slow走0步，fast走一步，fast是慢慢接近slow的，所以一定可以重合
	}
	此时就可以判断链表有环了。如何确定环的入口呢？
	
	3.当fast==slow的时候，设置链表前面有a个节点， 链表环有b个节点，
	fast走的距离是slow的两倍，f=2s
	fast比slow多走了n个环的长度，f = s+n*b,所以，slow走过的长度s=nb,f=2nb
	
	4.让指针一直走，走到链表入口的位置是，a+nb，绕了n圈，而slow指针只走了nb步数，只要再让slow指针走a步数，就能在入口处停下来，如何再让slow指针走a步数{
		1.将fast重新指向head头结点
		2.fast，slow重新开始走，再次重合是后，刚好走了a步数，fast，slow停留在入口位置
	}
	*/
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {// 有环
                fast = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}
//代码写出来很简单，但分析过程的时候可不简单

328.奇偶链表

/**
 * 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 oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode oddList = new ListNode();
        ListNode evenList = new ListNode();

        ListNode odd = oddList;
        ListNode even = evenList;
        boolean flag = true;
        while (head != null) {
            if (flag) {
                odd.next = head;
                odd = odd.next;
            } else {
                even.next = head;
                even = even.next;
            }
            head = head.next;
            flag = !flag;
        }
        even.next = null;
        odd.next = evenList.next;
        return oddList.next;
    }
}