【练习Day6】链表

1.编程题：链表相加

链接：链表相加(二)_牛客题霸_牛客网

方法一：栈

思路:

从题中给出的有效信息：

• 一个链表代表一个整数，返回多个链表的相加结果

故此顺位迭代就可以了，链表的问题大多借助栈和队列的结构思想

具体做法：
申请两个栈空间和一个标记位，然后将两个栈中内容依次相加，将结果倒插入新节点中。

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here

        LinkedList<Integer> list1 = new LinkedList<>(); //list1栈
        LinkedList<Integer> list2 = new LinkedList<>(); //list2栈
        putData(list1, head1); //入栈
        putData(list2, head2);
        ListNode newNode = null;
        ListNode head = null;
        int carry = 0; //标记进位
        while(!list1.isEmpty() || ! list2.isEmpty() || carry != 0) {
            int x = (list1.isEmpty()) ? 0 : list1.pop();  //依次从栈中取出
            int y = (list2.isEmpty()) ? 0 : list2.pop();
            int sum = x + y + carry; //与进位一起相加
            carry = sum / 10; //更新进位
            //将计算值放入节点
            newNode = new ListNode(sum % 10);
                        //更新下一个节点的指向
            newNode.next = head;
            head = newNode;
        }
        return head;

    }
    private static void putData(LinkedList<Integer> s1,ListNode head1) {
        if (s1 == null) s1 = new LinkedList<>();
                //遍历节点将其插入栈中
        while(head1 != null) {
            s1.push(head1.val);
            head1 = head1.next;
        }
    }
}

复杂度分析：

• 时间复杂度：O(max(m,n))，由于只遍历了一次，只需要看两个链表更长的
• 空间复杂度：O(m+n)，申请了两个栈来记录元素

方法二：反转链表法（推荐使用）

思路：

既然链表每个节点表示数字的每一位，那相加的时候自然可以按照加法法则，从后往前依次相加。但是，链表是没有办法逆序访问的，这是我们要面对第一只拦路虎。解决它也很简单，既然从后往前不行，那从前往后总是可行的吧，将两个链表反转一 下：

while(cur != null){
    //断开链表，要记录后续一个
    ListNode temp = cur.next;
    //当前的next指向前一个
    cur.next = pre; 
    //前一个更新为当前
    pre = cur; 
    //当前更新为刚刚记录的后一个
    cur = temp; 
}

即可得到个十百千……各个数字从前往后的排列，相加结果也是个位在前，怎么办？再次反转，结果不就正常了。

具体做法：

• step 1：任意一个链表为空，返回另一个链表就行了，因为链表为空相当于0，0加任何数为0，包括另一个加数为0的情况。
• step 2：相继反转两个待相加的链表。
• step 3：设置返回链表的链表头，设置进位carry=0.
• step 4：从头开始遍历两个链表，直到两个链表节点都为空且carry也不为1. 每次取出不为空的链表节点值，为空就设置为0，将两个数字与carry相加，然后查看是否进位，将进位后的结果（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历。
• step 5：返回前将结果链表再反转回来。

import java.util.*;
public class Solution {
    //反转链表
    public ListNode ReverseList(ListNode pHead) { 
        if(pHead == null)
            return null;
        ListNode cur = pHead;
        ListNode pre = null;
        while(cur != null){
            //断开链表，要记录后续一个
            ListNode temp = cur.next;
            //当前的next指向前一个
            cur.next = pre; 
            //前一个更新为当前
            pre = cur; 
            //当前更新为刚刚记录的后一个
            cur = temp; 
        }
        return pre;
    }
    
    public ListNode addInList (ListNode head1, ListNode head2) {
        //任意一个链表为空，返回另一个
        if(head1 == null) 
            return head2;
        if(head2 == null)
            return head1;
        //反转两个链表
        head1 = ReverseList(head1); 
        head2 = ReverseList(head2);
        //添加表头
        ListNode res = new ListNode(-1); 
        ListNode head = res;
        //进位符号
        int carry = 0; 
        //只要某个链表还有或者进位还有
        while(head1 != null || head2 != null || carry != 0){ 
            //链表不为空则取其值
            int val1 = head1 == null ? 0 : head1.val; 
            int val2 = head2 == null ? 0 : head2.val;
            //相加
            int temp = val1 + val2 + carry; 
            //获取进位
            carry = temp / 10; 
            temp %= 10; 
            //添加元素
            head.next = new ListNode(temp); 
            head = head.next;
            //移动下一个
            if(head1 != null) 
                head1 = head1.next;
            if(head2 != null)
                head2 = head2.next;
        }
        //结果反转回来
        return ReverseList(res.next); 
    }
}

复杂度分析：

• 时间复杂度：O(max(m,n))，其中m与n分别为两个链表的长度，翻转链表三次，复杂度分别是O(n)、O(m)、O(max(m,n))，相加过程也是遍历较长的链表
• 空间复杂度：O(1)，常数级指针，没有额外辅助空间，返回的新链表属于必要空间

2.链表操作选择

A ：p->next = p->next->next ，这一步操作将 `p` 所指向节点的下一个节点指向了下下个节点，直接跳过了原下一个节点，没有实现将 `r` 插入到 `p` 之后的目的，所以 A 选项错误。

B ：r->next = p; p->next = r->next ，先让 `r` 的下一个节点指向 `p` ，这不符合插入的逻辑；然后让 `p` 的下一个节点指向 `r` 的下一个节点，导致 `r` 无法正确插入到 `p` 之后，所以 B 选项错误。

C ：r->next = p->next; p->next = r ，先将 `r` 的下一个节点指向 `p` 的下一个节点，保存了原来 `p` 后面的链表结构；然后将 `p` 的下一个节点指向 `r` ，成功地将 `r` 插入到了 `p` 之后，所以 C 选项正确。

D ：r = p->next; p->next = r->next ，这只是对指针的重新赋值，没有完成将 `r` 插入到 `p` 之后的操作，所以 D 选项错误。

E ：r->next = p; p->next = r ，先让 `r` 的下一个节点指向 `p` ，不符合插入的逻辑，所以 E 选项错误。

F ：p = p->next->next ，这是让 `p` 跳过两个节点指向后面，没有涉及 `r` 的插入操作，所以 F 选项错误。

答案：C
 

3.链表地址选择

线索二叉树，lchild前驱结点，rchild后继结点

答案：C

4.编程题：链表的奇偶重排

链接：链表的奇偶重排_牛客题霸_牛客网

方法：双指针（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

如下图所示，第一个节点是奇数位，第二个节点是偶数，第二个节点后又是奇数位，因此可以断掉节点1和节点2之间的连接，指向节点2的后面即节点3，如红色箭头。如果此时我们将第一个节点指向第三个节点，就可以得到那么第三个节点后为偶数节点，因此我们又可以断掉节点2到节点3之间的连接，指向节点3后一个节点即节点4，如蓝色箭头。那么我们再将第二个节点指向第四个节点，又回到刚刚到情况了。

//odd连接even的后一个，即奇数位
odd.next = even.next; 
//odd进入后一个奇数位
odd = odd.next; 
//even连接后一个奇数的后一位，即偶数位
even.next = odd.next; 
//even进入后一个偶数位
even = even.next; 

这样我们就可以使用了两个同方向访问指针遍历解决这道题。

具体做法：

• step 1：判断空链表的情况，如果链表为空，不用重排。
• step 2：使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
• step 3：上述过程，每次遍历两个节点，且even在后面，因此每轮循环用even检查后两个元素是否为NULL，如果不为再进入循环进行上述连接过程。
• step 4：将偶数节点头接在奇数最后一个节点后，再返回头部。

import java.util.*;
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        //如果链表为空，不用重排
        if(head == null) 
            return head;
        //even开头指向第二个节点，可能为空
        ListNode even = head.next; 
        //odd开头指向第一个节点
        ListNode odd = head; 
        //指向even开头
        ListNode evenhead = even; 
        while(even != null && even.next != null){
            //odd连接even的后一个，即奇数位
            odd.next = even.next; 
            //odd进入后一个奇数位
            odd = odd.next; 
            //even连接后一个奇数的后一位，即偶数位
            even.next = odd.next; 
            //even进入后一个偶数位
            even = even.next; 
        } 
        //even整体接在odd后面
        odd.next = evenhead; 
        return head;
    }
}

复杂度分析：

• 时间复杂度：O(n)，遍历一次链表的所有节点
• 空间复杂度：O(1)，常数级指针，无额外辅助空间

5.编程题：判断一个链表是否为回文结构

链接：判断一个链表是否为回文结构_牛客题霸_牛客网

方法一：数组复制反转法

思路：

即然回文结构正序遍历和逆序遍历结果都是一样的，我们是不是可以尝试将正序遍历的结果与逆序遍历的结果一一比较，如果都是对应的，那很巧了！它就是回文结构！

这道题看起来解决得如此之快，但是别高兴太早，链表可没有办法逆序遍历啊。链表由前一个节点的指针指向后一个节点，指针是单向的，只能从前面到后面，我们不能任意访问，也不能从后往前。但是，另一个容器数组，可以任意访问，我们把链表中的元素值取出来放入数组中，然后判断数组是不是回文结构，这不是一样的吗？

具体做法：

• step 1：遍历一次链表，将元素取出放入辅助数组中。
• step 2：准备另一个辅助数组，录入第一个数组的全部元素，再将其反转。
• step 3：依次遍历原数组与反转后的数组，若是元素都相等则是回文结构，只要遇到一个不同的就不是回文结构。

import java.util.*;
public class Solution {
    public boolean isPail (ListNode head) {
        ArrayList<Integer> nums = new ArrayList();
        //将链表元素取出一次放入数组
        while(head != null){ 
            nums.add(head.val);
            head = head.next;
        }
        ArrayList<Integer> temp = new ArrayList();
        temp = (ArrayList<Integer>) nums.clone();
        //准备一个数组承接翻转之后的数组
        Collections.reverse(temp); 
        for(int i = 0; i < nums.size(); i++){
            int x = nums.get(i);
            int y = temp.get(i);
            //正向遍历与反向遍历相同
            if(x != y) 
                return false;
        }
        return true;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n为链表的长度，遍历链表转化数组为O(n)，反转数组为O(n)，后续遍历两个数组为O(n)
• 空间复杂度：O(n)，记录链表元素的辅助数组，及记录反转后数组

方法二：数组复制双指针

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

既然方法一我们已经将链表的值放入了数组中，数组是可以按照下标直接访问的，那干啥还要傻乎乎地用另一个数组来表示反转后的数组呢？我们直接从后往前遍历与从前往后遍历一同比较，利用两个指针对撞访问，不就少了很多额外的时间了吗？

具体做法：

• step 1：遍历一次链表，将元素取出放入辅助数组中。
• step 2：使用下标访问，两个下标代表两个指针，两个指针分别从数组首尾开始遍历，左指针指向开头，从左到右，右指针指向数组末尾，从右到左，依次比较元素是否相同。
• step 3：如果有不一样，则不是回文结构。否则遍历到两个指针相遇就好了，因为左指针到了右半部分都是右指针走过的路，比较的值也是与之前相同的。

import java.util.*;
public class Solution {
    public boolean isPail (ListNode head) {
        ArrayList<Integer> nums = new ArrayList();
        //将链表元素取出一次放入数组
        while(head != null){ 
            nums.add(head.val);
            head = head.next;
        }
        //双指针指向首尾
        int left = 0; 
        int right = nums.size() - 1;
        //分别从首尾遍历，代表正序和逆序
        while(left <= right){ 
            int x = nums.get(left);
            int y = nums.get(right);
            //如果不一致就是不为回文
            if(x != y) 
                return false;
            left++;
            right--;
        }
        return true;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n为链表的长度，遍历链表转化数组为O(n)，双指针遍历半个数组为O(n)
• 空间复杂度：O(n)，记录链表元素的辅助数组

方法三：长度法找中点（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

在数组中，我们可以借助双指针，一个从前往遍历前一半数组，另一个从后往前遍历后一半数组，依次比较值。链表中如果我们要用这样的思想，左指针从前往后很容易，直接的链表的遍历就可以了。但是右指针是真的没有办法从尾巴往前走，要是链表后半段的指针是逆序的就好了。

怎么样能让链表后半段的指针反过来，将后半段链表整体反转不就行了吗？如果我们将后半段链表整体反转，那么相当于后半段就是从末尾指向中间，就可以实现后半段的逆序遍历——按照指针直接走就可以了。

while(head != null){
    //断开后序
    ListNode next = head.next; 
    //指向前序
    head.next = prev; 
    prev = head;
    head = next;
}

怎么找到中点，只要得到链表长度以后，遍历一半长度就可以找到中点。

具体做法：

• step 1：遍历链表，统计链表的长度。
• step 2：将长度除2，遍历这么多位置，找到链表的中点。
• step 3：从中点位置开始，对链表后半段进行反转。
• step 4：与方法二类似，双指针左指针指向链表开头，右指针指向链表尾，此时链表前半段是正常的，我们也可以正常遍历，但是链表后半段所有指针都被我们反转逆序，因此我们可以从尾节点往前遍历。
• step 5：依次比较对应位置的元素值是否相等。

import java.util.*;
public class Solution {
    //反转链表指针
    ListNode reverse(ListNode head) { 
        //前序节点
        ListNode prev = null; 
        while(head != null){
            //断开后序
            ListNode next = head.next; 
            //指向前序
            head.next = prev; 
            prev = head;
            head = next;
        }
        return prev;
    }
    
    public boolean isPail (ListNode head) {
        ListNode p = head;
        int n = 0;
        //找到链表长度
        while(p != null){ 
            n++;
            p = p.next; 
        }
        //中点
        n = n / 2; 
        p = head;
        //遍历到中点位置
        while(n > 0){ 
            p = p.next;
            n--;
        }
        //中点处反转
        p = reverse(p);  
        ListNode q = head;
        while(p != null){
            //比较判断节点值是否相等
            if(p.val != q.val) 
                return false;
            p = p.next;
            q = q.next;
        }
        return true;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n为链表的长度，遍历链表找到长度为O(n)，后续反转链表为O(n)，然后再遍历两份半个链表
• 空间复杂度：O(1)，常数级变量，没有额外辅助空间

方法四：双指针找中点（推荐使用）

思路：

上述方法三找中点，我们遍历整个链表找到长度，又遍历长度一半找中点位置。过程过于繁琐，我们想想能不能优化一下，一次性找到中点。

我们首先来看看中点的特征，一个链表的中点，距离链表开头是一半的长度，距离链表结尾也是一半的长度，那如果从链表首遍历到链表中点位置，另一个每次遍历两个节点的指针是不是就到了链表尾，那这时候我们的快慢双指针就登场了：

具体做法：

• step 1：慢指针每次走一个节点，快指针每次走两个节点，快指针到达链表尾的时候，慢指针刚好到了链表中点。
• step 2：从中点的位置，开始往后将后半段链表反转。
• step 3：按照方法三的思路，左右双指针，左指针从链表头往后遍历，右指针从链表尾往反转后的前遍历，依次比较遇到的值。

import java.util.*;
public class Solution {
    //反转链表指针
    ListNode reverse(ListNode head) { 
        //前序节点
        ListNode prev = null; 
        while(head != null){
            //断开后序
            ListNode next = head.next; 
            //指向前序
            head.next = prev; 
            prev = head;
            head = next;
        }
        return prev;
    }
    
    public boolean isPail (ListNode head) {
        //空链表直接为回文
        if(head == null) 
            return true;
        //准备快慢双指针
        ListNode slow = head; 
        ListNode fast = head;
        //双指针找中点
        while(fast != null && fast.next != null){ 
            slow = slow.next;
            fast = fast.next.next;
        }
        //中点处反转
        slow = reverse(slow);  
        fast = head;
        while(slow != null){ 
            //比较判断节点值是否相等
            if(slow.val != fast.val) 
                return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n为链表的长度，双指针找到中点遍历半个链表，后续反转链表为O(n)，然后再遍历两份半个链表
• 空间复杂度：O(1)，常数级变量，没有额外辅助空间

方法五：栈逆序（扩展思路）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

同样的，逆序访问我们不一定需要借助可以随机访问的数组，或者反转链表，我们还可以借助先进先出的栈：根据链表顺序入栈的元素，越在前面的就越在栈底，越在后面的就越在栈顶，因此后续从栈中弹出的元素，依次就是链表的逆序。

具体做法：

• step 1：遍历链表，将链表元素依次加入栈中。
• step 2：依次从栈中弹出元素值，和链表的顺序遍历比较，如果都是一一比较相同的值，那正好就是回文，否则就不是。

import java.util.*;
public class Solution {
    public boolean isPail (ListNode head) {
        ListNode p = head;
        Stack<Integer> s = new Stack();
        //辅助栈记录元素
        while(p != null){ 
            s.push(p.val);
            p = p.next;
        }
        p = head;
        //正序遍历链表，从栈中弹出的内容是逆序的
        while(!s.isEmpty()){ 
            //比较是否相同
            if(p.val != s.pop()) 
                return false;
            p = p.next;
        }
        return true;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n为链表的长度，遍历链表入栈为O(n)，后续再次遍历链表和栈
• 空间复杂度：O(n)，记录链表元素的辅助栈长度和链表相同