标签：Node 结点 head next 链表算法 004 null

哈希表

哈希表增删改查是常数时间，但是这个常数时间比较大
放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用就是这个东西的内存地址的大小

有序表

有序表的增删改查是O(logn)级别的
放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用就是这个东西内存地址的大小

链表

反转单向和双向链表

https://leetcode.cn/problems/reverse-linked-list/

分别实现反转单向链表和反转单向链表的函数

如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)

package com.algorithm.class04;

public class Code01_ListReverse {
	//单链表结点
	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; }
	}
	
    //反转单向链表
	public ListNode reverseList(ListNode head) {
		ListNode pre = null;
		ListNode next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}
	
	//-----------------------------------------------------------------------------------------
	
	//双链表结点
	public class DoubleListNode {
		int value;
		DoubleListNode last;
		DoubleListNode next;

		DoubleListNode(int v) {
			value = v;
		}
	}
	
    //反转双向链表
	public DoubleListNode reverseList2(DoubleListNode head) {
		DoubleListNode pre = null;
		DoubleListNode next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			head.last = next;
			pre = head;
			head = next;
		}
		return pre;
	}
}

打印两个有序链表的公共部分

给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。

如果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)

head1指向第一个链表，head2指向第二个链表

比较两个指针指向的结点：

较小的那个结点的指针往后移动

如果相等，就是链表的公共部分，打印

package com.algorithm.class04;

public class Code02_PrintCommonPart {
	public class Node {
		int value;
		Node next;
		Node(int data) {
			this.value = data;
		}
	}
	
	public void printCommonPart(Node head1, Node head2) {
		System.out.print("Common Part: ");
		while (head1 != null && head2 !=null) {
			if (head1.value < head2.value) {
				head1 = head1.next;
			}else if (head1.value > head2.value) {
				head2 = head2.next;
			}else {
				System.out.println(head1.value + " ");
				head1 = head1.next;
				head2 = head2.next;
			}
			System.out.println();
		}
	}
}

判断一个链表是否是回文结构

LCR 027. 回文链表 - 力扣（LeetCode）

给定一个单链表的头结点head，请判断该链表是否为回文结构

如果链表长度为N，时间复杂度为O(N)，额外空间复杂度为O(1)

不同空间复杂度的实现方法：

额外空间O(n)：将链表的结点依次入栈，然后每弹出一个结点，就与链表的结点比较

额外空间O(n/2)：只把链表的后半部分结点入栈，栈中的结点与链表前半部分比较。就相当于把链表对折，比较对折后的两半是否一样

用快慢结点的方式找到链表的中点

额外空间O(1)：翻转后半部分链表，·

额外空间复杂度O(n)

把所有结点都入栈，然后再出栈

每弹出一个，就和链表的结点依次进行比较

弹出的顺序刚好是从尾到头，链表的顺序又是从头到尾

public boolean isPalindrome1(Node head) {
    Stack<Node> stack = new Stack<>();
    Node cur = head;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    while (head != null) {
        if (head.value != stack.pop().value) {
            return false;
        }
        head = head.next;
    }
    return true;
}

额外空间复杂度O(n/2)

用快慢指针找到链表的中点

把链表的右半部分入栈

然后依次弹出，和左半边的链表进行比较

就相当于比较链表的左半部分和右半部分

而关于中点：

快慢指针都指向第一个结点，最后慢指针指向会：如果是奇数个就指向中点，如果是偶数个就指向第n/2个
快指针先走一步，奇数个时慢指针指向中点，偶数个时指向中点的下一个
快指针先走两步，奇数个时慢指针指向中点的前一个，偶数个时指向中点的上一个

public boolean isPalindrome2(Node head) {
    //链表为空或者链表只有一个结点
    if (head == null || head.next == null) {
        return true;
    }
    /**写法一：
		 * 慢指针指向的结点就是第一个要入栈的结点
		 * 奇数个时慢指针指向中点，偶数个时指向第n/2+1
		 */
    Node slow = head;
    Node fast = head;
    /**写法二
		 * 回文链表可以看成两半，重叠的结点不进行比较
		 * 最终慢指针指向的是右边第一个不重复的结点，比如1 2 3 2 1：则指向右边的2；1 2 3 3 2 1，也是指向右边的2n
		 */
    // Node slow = head.next;
    // Node fast = head;

    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }

    Stack<Node> stack = new Stack<>();
    //把后半部分入栈
    while (slow != null){
        stack.push(slow);
        slow = slow.next;
    }

    //比较
    while (!stack.isEmpty()){
        if (head.value != stack.pop().value){
            return false;
        }
        head = head.next;
    }
    return true;
}

额外空间复杂度O(1)

快慢指针找到链表的中点，如果是奇数个就慢指针就指向中点处，如果是偶数个就指向中点的下一个

翻转右半边的链表

然后比较两个半链表是否一样

public boolean isPalindrome3(Node head){
    if (head == null || head.next == null){
        return true;
    }

    //找到中点 奇数个时刚好是中点，偶数个时是第n/2个结点
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }

    //翻转右半边链表
    Node pre = null;
    Node cur = slow;
    Node next = null;
    while (cur != null){
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }//pre指向翻转后的右边链表的头结点

    //判断左右链表是否相同
    Node head_left = head;
    Node head_right = pre;
    boolean res = true;
    while (head_left != null && head_right != null){
        if (head_left.value != head_right.value){
            res = false;
            break;
        }
        head_left = head_left.next;
        head_right = head_right.next;
    }

    //把右边链表翻转回来
    cur = pre;
    pre = null;
    while (cur != null){
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return res;
}

将单向链表按某值划分成左边小、中间相等、右边大的形式

给定一个单链表的头结点head，结点的值类型都是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是小于pivot的结点，中间都是等于pivot的结点，右部分都是大于pivot的结点

把结点存储到数组中，然后后面就是荷兰国旗问题

public Node listPartition1(Node head, int pivot){
    if (head ==null){
        return head;
    }
    Node cur = head;
    // int i = 0;
    // while (cur != null){
    //     i++;
    //     cur = cur.next;
    // }
    //把链表的结点放入数组中
    List<Node> nodeList = new ArrayList<>();
    while (cur != null){
        nodeList.add(cur);
        cur = cur.next;
    }
    //划分
    arrPartition(nodeList, pivot);
    //将划分好的结点放入原链表中
    int i;
    for (i = 1; i < nodeList.size(); i++){
        nodeList.get(i - 1).next = nodeList.get(i);
    }
    nodeList.get(i - 1).next = null;
    return nodeList.get(0);
}

public void arrPartition(List<Node> nodeArr, int pivot){
    int small = -1;//小于区
    int big = nodeArr.size();//大于区
    int index = 0;//指向当前遍历的结点

    while (index < big){
        if (nodeArr.get(index).value < pivot){//如果当前结点小于pivot，就要把它放在小于区；放在小于区的下一个位置，同时扩大小于区
            swap(nodeArr, index++, ++small);//交换，同时扩大小于区
        }else if (nodeArr.get(index).value > pivot){//放在小于区同时扩大大于区
            swap(nodeArr, index, --big);//这里index不++，因为大于区的前一个结点，是没有经过比较的，不知道它的大小；而上面的index++，是因为index已经在小于区边界的后面的，那么边界到index这之间的结点一定是等于pivot的
        }else {//等于pivot，继续比较下一个结点
            index++;
        }
    }
    for (Node node : nodeArr) {
        System.out.println(node);
    }
}

public void swap(List<Node> nodeArr, int a, int b){
    Node temp = nodeArr.get(a);
    nodeArr.set(a, nodeArr.get(b));
    nodeArr.set(b, temp);
}

在实现原问题功能的基础上增加如下的要求

调整后所有小于pivot的结点之间的相对顺序和调整前一样
调整后所有等于pivot的结点之间的相对顺序和调整前一样
调整后所有大于pivot的结点之间的相对顺序和调整前一样
时间复杂度达到O(N)，额外空间复杂度达到O(1)

只用链表实现，不用数组

6个变量，分别是：小于区的头指针和尾指针，等于区的头指针和尾指针，大于区的头指针和尾指针

初始时每个区的头尾指针指向null，当有第一个结点进入时，头指针就指向这个结点

遇到小于pivot的结点时，接入到小于区的链表，然后更新尾指针指向该结点

遇到等于pivot的结点时，接入到等于区的链表，然后更新尾指针指向该结点

遇到大于pivot的结点时，接入到大于区的链表，然后更新尾指针指向该结点

最后将三个链表连接起来

public Node listPartition2(Node head, int pivot){
    Node small_head = null;
    Node small_tail = null;
    Node equal_head = null;
    Node equal_tail = null;
    Node big_head = null;
    Node big_tail = null;
    Node next = null;

    while (head != null){
        next = head.next;
        head.next = null;//使得每个结点在进入自己的区域的时候是独立的，断开自己区域的尾结点，如果不这样断开，尾结点可能还连接的有结点，这个结点可能不属于这个区域，会有不该有的指针指向不该有的结点，画图
        if (head.value < pivot){//小于区
            if (small_head == null){//是小于区的第一个结点，也就是小于区的头结点
                small_head = head;
                small_tail = small_head;//更新尾结点
            }else {
                small_tail.next = head;
                small_tail = small_tail.next;
            }
        } else if (head.value > pivot) {//大于区
            if (big_head == null){
                big_head = head;
                big_tail = big_head;
            }else {
                big_tail.next = head;
                big_tail = big_tail.next;
            }
        }else {//等于区
            if (equal_head == null){
                equal_head = head;
                equal_tail = equal_head;
            }else {
                equal_tail.next = head;
                equal_tail = equal_tail.next;
            }
        }
        head = next;
    }
    //连接小于区和等于区
    if (small_tail != null){//可能没有小于的数
        small_tail.next = equal_head;
        //有等于的数就把小于区和等于区相连，没有的话就将small_tail指向equal_tail，以便于后面和大于区相连  把当前存在的链表的末尾当成等于区的末尾
        equal_tail = equal_tail == null ? small_tail : equal_tail;
    }
    //连接等于区和大于区
    if (equal_tail != null){
        equal_tail.next = big_head;
    }
    //每个区都可能为空，返回不为空的头就是整个链表的头结点
    return small_head != null ? small_head : equal_head != null ? equal_head : big_head;
}

复制含有随机指针结点的链表

rand指针是单链表结点结构中新增的指针，rand可能指向链表中的任意一个结点，也可能指向null。给定一个由Node结点类型组成的无环单链表的头结点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头结点。要求时间复杂度O(N)，额外空间复杂度O(1)

空间复杂度O(N)

用一个哈希表存储链表的所有结点，那么1’的next就是1的next复制后的结点，也就是map.get(1->next)这个结点。同理1‘的rand也是根据1的rand找到的

public Node copyListWithRand1(Node head){
    HashMap<Node, Node> map = new HashMap<>();
    Node cur = head;
    while (cur != null){
        map.put(cur, new Node(cur.value));
        cur = cur.next;
    }
    cur = head;
    while (cur != null){
        map.get(cur).next = map.get(cur.next);//1'->next是1->next复制过来的结点，这个结点存储在map中，key是1->next
        map.get(cur).rand = map.get(cur.rand);
        cur = cur.next;
    }
    return map.get(head);
}

空间复杂度O(1)

链表的每个结点都复制一个连接到原始结点的后面，指针的指向不变

1的rand指向3，就说明1'的rand指向了3‘，而3’又是3的next。

两个单链表相交

给定两个可能有环也可能无环的单链表，头结点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个结点。如果不相交，返回null。

要求如果两个链表长度之和为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

求链表的相交结点有以下三种情况：

两个无环链表

两个有环链表

一个有环一个无环

所以要先判断链表是否有环

主调用函数

//链表的相交结点
public Node getIntersectNode(Node head1, Node head2){
    if (head1 == null || head2 == null){
        return null;
    }

    //寻找两个链表的入环结点
    Node loop1 = getLoopNode(head1);
    Node loop2 = getLoopNode(head2);

    //两个链表都无环
    if (loop1 == null && loop2 == null){
        return noLoop(head1, head2);
    }
    //两个链表都有环
    if (loop1 != null && loop2 != null){
        return bothLoop(head1, loop1, head2, loop2);
    }
    //其中一个链表有环，不会相交
    return null;
}

先判断链表是否有环

设置快慢指针，慢指针每次走一步，快指针每次走两步。相遇之后，慢指针停在原地，快指针指向头结点。快慢指针每次移动一步，再次相遇的时候一定是入环结点处。

//找到第一个人入环节点，如果无环，返回null
public Node getLoopNode(Node head){
    //结点数小于3不会形成环
    if (head == null || head.next == null || head.next.next == null){
        return null;
    }
    Node slow = head.next;
    Node fast = head.next.next;//由于while的判断条件限制，slow和fast不能都设置为head  这里设置为slow、fast分别已经走了一步和两步
    //查找首次相遇的结点
    while (slow != fast){
        if (fast == null || fast.next == null){//链表无环
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    fast = head;//快指针指向头结点
    while (slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;//再次相遇时就是入环结点
}

情况一：两个无环单链表相交

遍历链表1，记尾结点end1，长度len1；遍历链表2，记尾结点end2，长度len2。
如果end1 != end2，则两个链表一定不相交。（看图）。否则：
两个链表的长度的差值x，长链表先走x步。然后两个链表一起走
第一个相同的结点就是它们的相交结点

public Node noLoop(Node head1, Node head2){
    if (head1 == null || head2 == null){
        return null;
    }
    Node cur1 = head1;
    Node cur2 = head2;
    int size1 = 1;
    int size2 = 1;
    //遍历两个链表，同时计算两个链表的长度
    while (cur1.next != null){//判断条件是cur1.next，因为后面要判断两条链表的 最后一个结点是否相同
        size1++;
        cur1 = cur1.next;
    }
    while (cur2.next != null){
        size2++;
        cur2 = cur2.next;
    }
    //最后一个结点不相同，说明两条链表没有相交
    if (cur1 != cur2){
        return null;
    }
    int d = size1 - size2;
    //d>0说明链表1更长
    cur1 = d > 0 ? head1 : head2;//cur1代表长链表
    cur2 = cur1 == head1 ? head2 : head1;//cur2就是另一条链表
    d = Math.abs(d);
    //长链表先走d步
    while (d > 0){
        cur1 = cur1.next;
        d--;
    }
    //相交结点
    while (cur1 != cur2){
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return cur1;
}

情况二：两个链表都有环

1.两个链表不相交

先求两个链表的入环结点loop1和loop2

链表1先走，走的过程中如果没有遇到loop2，那么就是第1种

如果遇到了loop2，就是第3种情况。这时loop1和loop2都是第一个相交结点，只是一个离链表1近，一个离链表2近
2.相交时，入环结点相同，共用环

可以看作是无环链表求相交结点。

把它们的入环结点当作两个链表的尾结点，丢弃环，就变成了无环链表求相交结点
3.入环结点不同，共用环

//两个链表都有环
public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
    Node cur1 = null;
    Node cur2 = null;
    //入环结点相同，看作无环链表相交问题
    if (loop1 == loop2){
        cur1 = head1;
        cur2 = head2;
        int size1 = 0;
        int size2 = 0;
        while (cur1 != loop1){//注意这里判断的是是否等于loop1，无环链表的尾结点这里是空的，但这里有环链表相交，我们只是看作无环链表不是真的无环
            size1++;
            cur1 = cur1.next;
        }
        while (cur2 != loop2){
            size2++;
            cur2 = cur2.next;
        }
        int d = size1 - size2;
        cur1 = d > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        d = Math.abs(d);
        while (d > 0){
            cur1 = cur1.next;
            d--;
        }
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }else {//入环结点不同
        cur1 = loop1.next;//先走一步，否则进不了while
        while (cur1 != loop1){//cur1走一圈的过程中，是否会遇到loop2
            if (cur1 == loop2){//链表1遍历的过程中遇到了链表2的入环结点
                return loop1;
            }
            cur1 = cur1.next;
        }
        return null;
    }
}

情况三：一个链表有环，一个链表无环

两个链表一定不相交

标签：Node,结点,head,next,链表,算法,004,null
From： https://www.cnblogs.com/jyyyy/p/17994226

【算法】004_链表

哈希表

有序表

链表