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 hereLinkedList<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)，记录链表元素的辅助栈长度和链表相同
