Unit 2 链表

Unit 2 链表

Q1：打印两个有序链表的公共部分
Q2：删除链表中倒数第n个结点
Q3：删除链表的中间结点+删除链表(a/b)处的结点
Q4：反转单向链表和双向链表
Q5：反转链表中部分结点
Q6：约瑟夫问题
Q7：判断链表是否回文
Q8：给定一个pivot，将链表重组为左边比pivot小，中间跟他一样大，右边比pivot大的形式
Q9：复制(深度拷贝)含随机指针结点的链表。(复制复杂链表)
Q10：两个单链表逐位相加，生成相加链表
Q11：给定两个单链表，如果相交则返回相交的第一个结点；如果不相交返回Null
Q12：将单链表的每k个结点之间逆序
Q13：删除无序单链表中值重复出现的结点
Q14：删除单链表中值为num的结点
Q15：将二叉排序树转换成双向链表
Q16：对单链表做选择排序
Q17：给定一结点，以O(1)的时间复杂度删除之
Q18：在有序环形单链表中插入新结点
Q19：合并有序单链表
Q20：将单链表分成左右两个半区，重新组合链表，成左半区一个右半区一个，左半区一个右半区一个的形式
Q21：从尾到头打印链表

unit 2 Q1:打印两个有序链表的公共部分

time:2019/07/10
思路：
同时遍历两个链表，谁小谁向右移一位，如果相同则输出后都右移一位，直到其中一个到头为止。
简单题。

代码：U2Q1_PrintCommon.java

 

unit 2 Q2:删除链表中倒数第n个结点

time:2019/07/11
思路：
双指针法。后指针rear先走n个，随后前指针front和rear一起向后走，走到rear到头为止。此时front指向的便是倒数第n个结点，删除之。
简单题。

代码：U2Q2_RemoveNthNode.java

 

unit 2 Q3:删除链表的中间结点+删除链表(a/b)处的结点

time:2019/07/11
思路：
删除中间结点：快慢指针法。每一步快指针rear右移2，慢指针front右移1，直到rear到头为止，front指向的即是中间结点，删除之。
删除a/b处结点：1.快慢指针法。每一步快指针rear右移b，慢指针front右移a，同上。
2.先算出链表总长度length。再length*(a/b)，对结果向上取整，即为要删除的元素，删除之。
简单题。

代码：U2Q3_removeMid.java

 

unit 2 Q4:反转单向链表和双向链表

time:2019/07/13
思路：
反转单向链表和双向链表的思路都是使用头插法。
头插法每次插入时包含两个操作：
1.取出该结点，不要让链断裂；
2.将该结点插入至最头部。

        //头插法反转单链表核心code
        while(cur!=null){
            temp=cur.next;
            pre.next=cur.next;//取出cur结点
            cur.next=head;//将cur插入头部
            head=cur;//更新head
            cur=temp;//更新cur
        }

反转单链表图示：

反转双链表图示：

代码：U2Q4_ReverseLink.java

 

unit 2 Q5:反转链表中部分结点

要求：
给定两个整数from和to,反转单向链表中第from个结点到第to个结点
1.时间复杂度O(N),空间复杂度O(1)
2.如果不满足1<=from<=to<=N,不反转直接返回
time:2019/07/14
思路:
1.找到位置后用头插法反转链表。
2.记录需反转部分的头结点headPart，和headPart的上一个结点pre_headPart，每次的cur插在pre_headPart和headPart之间。
3.如果from==1，注意返回headPart而不是head。(head被反转到后面去了）

代码：U2Q5_ReversePart.java

 

unit 2 Q6:约瑟夫问题

编号为1-N的N个士兵围坐成一个圈，从编号为1的士兵开始以1、2、3的顺序报数，数到m的士兵被杀死出列。之后的士兵再从1开始报数，直到只剩一个士兵，求该士兵的编号。
time:2019/07/15
思路：
两种方法，一种是常规的循环链表法，时间复杂度O(n$\times$×m);
另一种是递归方法，时间复杂度O(n)。

• 循环链表法：
  设置计数器count。循环遍历链表，每次遍历count累加。每当count==3时，删除该元素并重置count为1。直至链表只剩一个元素为止。

• 递归法
  规则告诉我，每次出队都要重新报数，可以理解为每删一个人，每个人对应的要叫到的号都会变一次。约瑟夫问题就是求最后出去的那个人在最开始的链表中排几号。

  根据常识，只剩一个人的时候，他肯定是叫1，然后没人接，因此最后的幸存者在最后一次淘汰时的叫号是1。如果能通过寻找淘汰后叫号和淘汰前叫号之间的关系，即通过幸存者倒数第一次的叫号找到倒数第二次的叫号，再通过倒二的叫号找到倒三的叫号，一路向上，就可以找到幸存者在最初的链表中排几号。
  
  总结上图可得：设old为淘汰前一个结点的叫号，new为淘汰后该结点的叫号，则old和new之间可以建立关系：old=(new+m-1)%n+1；
  通过淘汰前后叫号的映射关系，构造递归函数，即可从最后的叫号1一路反推出该结点在最初链表中的叫号，并返回最初叫号。
   
  Q:为啥不建立更直白的关系：old=(new+m)%n?
  A:计数从1开始，如果令old=(new+m)%n，则当new+m==n时，old传上去永远是0。不能让叫号出现0，最小也得是1。所以使用 old=(new+m-1)%n+1。

    //递归求解约瑟夫问题,时间复杂度O(n)
    public int get(int n,int m){
        if(n==1) return 1;
        return (get(n-1,m)+m-1)%n+1;
    }

代码：U2Q6_Josephus.java

 

unit 2 Q7:判断链表是否回文

time：2019/07/17
思路：
两种方法。

• 借用栈实现（时间复杂度O(n)，空间复杂度O(n)）
  先遍历一遍，将各结点值依次入栈。再依次弹出，和链表从左至右的顺序进行比较：全对的上则回文，反之不回文。
• 奇技淫巧（时间复杂度O(n)，空间复杂度O(1)）
  1 . 设快慢指针，慢走1步快走2步。快指针fast最终停在最后，慢指针slow指向中间。（例：如1->2->3->2->1，则slow指向3、fast指向1。 如1->2->3->3->2->1，则slow指向第一个3、fast指向2。
  2 .将链表从中间断开。头插法反转右半部分。
  3 .依次比较左半部分和反转后的右半部分，如果全对的上则回文，反之不回文。
  PS：无论是否回文，都需要还原链表，修复犯罪现场。

代码：U2Q7_Palindrome.java

 

unit 2 Q8:给定一个pivot，将链表重组为左边比pivot小，中间跟他一样大，右边比pivot大的形式

要求：左、中、右三部分内部各结点顺序，要求和原链表顺序保持一致。
时间复杂度O(N),空间复杂度O(N)
time:2019/07/18
思路：
1.设置三个链表,small、equal、large。
2.遍历原链表，根据value大小分别将其添加入对应分链表，最后将三部分再合起来就可以。
PS:思路不难，但实现中细节很多，考察基本功。
如遍历时取出当前点cur，需置cur.next=null，不然最后一个cur会指向原来的下一结点，很麻烦。

代码：U2Q8_leftSmall_rightLarge.java

 

unit 2 Q9:复制(深度拷贝)含随机指针结点的链表。(复制复杂链表)

要求：现有一特殊的链表结点RandNode,它在正常的Node基础上加了rand指针，rand指针可以随意指向链表中任何结点或null.

//添加随机指针rand的特殊链表结点RandNode
public class RandNode {
    public int value;
    public RandNode next;
    public RandNode rand;
    public RandNode(int data){
        this.value=data;
    }
}

要求时间复杂度O(n),空间复杂度O(1)。
time：2019/07/18
思路：
1.遍历，对每一个RandNode结点都创建一个新的副本，该副本结点正好插在原结点的后面。

例：原链表:1->2->3->null，在各结点后添加副本操作后，则链表变为：1->1’->2->2’->3->3’->null

2 再遍历，此次遍历设置每一副本结点的指针。(每一副本结点的rand指向的应是，该副本结点对应原结点的rand指针对应的结点的下一个)

例：3结点的rand指针指向1结点。则相应地，3’结点的rand指针应指向1’结点，1‘即是1结点的下一个结点）

//设置副本结点rand指针の关键code
curCopy=cur.next;
curCopy.rand=(cur.rand!=null)?(cur.rand.next):null;

3 间隔取出各副本结点，连成一个单独链表，返回。

代码：U2Q9_CopyRandLink.java

 

unit 2 Q10:两个单链表逐位相加，生成相加链表

要求：如果有Link1：1->2->3->5->6，Link2：2->4->5->7，因为12356+2457=14813，所以题目要求生成新链表newLink：1->4->8->1->3。 时间复杂度O(n)，空间复杂度O(1)
time:2019/07/20
思路：
1.将两链表逆序。
2.一起向后遍历，逐位相加。置一carry存进位，初值为0，如果（Link1中的数+Link2中的数+carry）>10则将进位carry置为1。将【相加后的数】除以10的余数，添加为新链表的一个结点
3.两链表都走完后，如果进位carry==1，则还需给新链表添加一个1结点
4.反转新链表，即得相加链表。

代码：U2Q10_AdditiveLink.java
 

unit 2 Q11:给定两个单链表，如果相交则返回相交的第一个结点；如果不相交返回Null

要求：如果Link1的长度为M，Link2的长度为N，则时间复杂度O(N+M)，空间复杂度O(1)
time：2019/07/21
插图参考博客
思路：
该问题要分成三个问题：

Question1:如何判断单链表是否有环？
Answer1:
1.设置快fast、慢slow指针，慢走1快走2。
2.如果fast能走到null，说明链表没有环；
反之如果有环，则fast永远走不到null，且fast和slow必然相遇。

Question2:如果有环，找出环的第一个结点？
Answer2:
接着Question1步骤
3.fast与slow相遇后，slow不动。置一cur从头开始以步长为1，与slow指针一起向后走。当slow指针和cur指针相遇时，cur所指结点即是环首结点。

证明如下：

如图，设从头结点至环首结点的长度为len，环首至slow与fast交汇点的长度为x，环的长度为R。
设slow已走过的长度为d，可知d=len+x。因为快2慢1，fast走过的长度为2d，2d=len+nR+x(n是圈数，n>=1)。联立二式可得len=nR-x(n>=1)
cur从头走到环首需要 len=nR-x 步，此时slow也在环中走了 (nR-x)步。
又slow的初始位置(slow与fast相遇处)距环首 x 步，则当cur走至环首时，slow与环首相距 x+nR-x=nR步，得slow也刚好在环首。得证。

Question3:给定两个链表是否相交？返回相交的第一个结点
Answer3:
两链表都有环、或者都无环才有可能相交。如果一个无环、一个有环，则不可能相交。
1.两Link都无环：

• 置cur1遍历 Link1 至最后，记录最后一个结点end1、链表长度len1。置cur2遍历 Link2 至最后，记录最后一个结点end2、链表长度len2。如果end1==end2，则两链表相交，反之不相交。
• 如果相交：将cur1和cur2指向各自的头部。哪个链表长，就让长链表的指针先走|len1-len2|步。再之后一起向右走，第一次走到一起，即是两链表相交的第一个结点。

2.两Link都有环：
置cur1从Link1的环首结点开始遍历，如果cur1绕着Link1的环转了一圈还没有碰到Link2的环首结点，说明两个Link不相交。
反之cur1已碰到Link2的环首结点，则两链表相交，返回Link1或者Link2的环首结点均可。（Link1的环首结点和Link2的环首结点都在公共环上，谁都可以说自己是环首结点，返回哪个都行）

 

unit 2 Q12:将单链表的每k个结点之间逆序

要求：如果链表为 1->2->3->5->6，k为2，则操作后链表为 2->1->5->3->6
时间复杂度O(N)，空间复杂度O(1)
time：2019/07/23
思路：
1.设置ReversePart(pre_headPart，headPart，end)，用以反转一部分链表
pre_headPart：指向需反转子链表头结点的前一结点
headPart：指向需反转的子链表的头结点
end：指向需反转的子链表的尾结点
使用不断链的头插法反转子链表。可参考 unit 2 Q5 ReversePart (点击跳转)
2.每次计数走到第k个就执行ReversePart反转。
知易行难
代码：U2Q12_ReverseKNode.java

 

unit 2 Q13：删除无序单链表中值重复出现的结点

例：1->2->3->3->4->4->2->1->1->null，删除值重复的结点后：1->2->3->4->null
time:2019/07/24
思路：
两种方法。
方法一：使用 HashTable记录出现过的值，每轮遍历时去hashtable处找，出现过便删除。
因查找hashtable的时间复杂度为O(1)，所以该方法的时间复杂度为O(N)，空间复杂度为O(N)
方法二：像选择排序一样，每轮遍历都要删除后面跟当前结点一样的结点。
时间复杂度O($N^2$N2)，空间复杂度O(1)。

代码：U2Q13_RemoveDuplicate.java

 

unit 2 Q14：删除单链表中值为num的结点

time：2019/07/25
思路：
基础题。时间复杂度O(N)，空间复杂度O(1)
注意一点即可，需要找到第一个不等于num的结点作为头结点 while(head.value==num) head=head.next;

代码：U2Q14_removeNum.java

 

unit 2 Q15：将二叉排序树转换成双向链表

要求不建立新的结点；时间复杂度为O(N)。
经典题，剑指offer 第36题 + Leetcode 第114题 难度:中等
date：2019/09/30
思路：
用队列queue收集二叉树递归中序遍历结果；再一个个出队列后建成有序双链表。
树结点的lchild相当于双链表的left,树节点的rchild相当于双链表的right。
此方法额外空间复杂度为O(N)

代码：U2Q15_BSTtoDList.java

 

unit 2 Q16：对单链表做选择排序

要求：时间复杂度O($N^2$N2)，空间复杂度O(1)
time：2019/07/25
思路：
方法一：模仿选择排序的数组版本，不拆指针，仅交换链表结点的值。

方法二：拆指针，面试官可能会要求。实现起来坑很多。
1.设置head,tail分别指向已排序链表的头结点和尾结点，初值均为null；
设置headPart指向未排序链表的头结点，初值为link；
设置small用来接getPreSmallNode()函数传回的未排序链表的最小结点
设置一getPreSmallNode(Node head)函数，返回最小结点small的上一个结点
2.未排序链表不空则Loop:

1. 调用getPreSmallNode()找到未排序链表中最小值结点small
2. 将small结点取出，添加到已排序链表中
3. 更新headPart
   PS：如果最小结点small刚好就是headpart，则headPart会被加入已排序链表，headPart需右移一位。反之，small在headPart后面，small拆了加入已排序链表之后，未排序链表会变短，可是头结点还是当前的headPart，headPart不用变化。

代码：U2Q16_LinkSelectSort.java

 

unit 2 Q17：给定一结点，以O(1)的时间复杂度删除之

time：2019/07/27
思路：
将待删除结点的next结点的值赋给该节点，删除下一个结点即可
副作用：不能删除最后一个结点（想删除最后一个结点，一定要找到该结点的位置）

代码：U2Q17_RemoveNodeWired.java

 

unit 2 Q18：在有序环形单链表中插入新结点

有序环形单链表升序排列，给定一个num，创建num对应结点并将它插入合适的位置
time：2019/07/27
思路：
1.如果链表为空，返回新结点newNode。
2.设置pre从头结点，cur从头结点的下一结点，遍历链表。遇到 pre.value<=num<=cur.value时break跳出循环。
3.跳出遍历的while循环后，有三种情况。

1. 中间找到插入位置，遂break
2. 值比pre.value还小，遍历一轮后出循环
3. 值比最后一个还大，遍历一轮后出循环

无论上述哪种情况，都要将newNode插入pre和cur之间。
4.之后要返回头结点head。只有一种情况需要更新head：给定num比当前头结点还要小，head指向新的newNode。其他情况是将newNode加到后面，所以head不变。

代码：U2Q18_InsertCircularList.java

 

unit 2 Q19：合并有序单链表

time：2019/07/28
思路：
1.取head1,head2中较小者作为新链表的头结点head
2.置cur1,cur2分别遍历两链表，取二者中较小者插入新链表的最后，如此循环
3.有一个链表被取完则跳出循环，此时将另一链表的剩余部分直接挂在新链表后即可

代码：U2Q19_MergeOrderedList.java

 

unit 2 Q20：将单链表分成左右两个半区，重新组合链表，成左半区一个右半区一个，左半区一个右半区一个的形式

例：1->2->3->4->null 调整为 1->3->2->4->null
1->2->3->4->5->null 调整为 1->3->2->4->5->null
time：2019/07/29
思路：
1.设置快慢指针，找到左半区的尾结点和右半区的头结点，将左、右拆开
2.设置merge()函数，按一轮循环添加一次左结点再添加一次右结点的方式，直至左边为空。因为len(右)>=len(左)，将右边最后一个加入末尾即得新链表，返回之。

代码：
U2Q20_Relocate.java

 

unit 2 Q21：从尾到头打印链表

输入链表头结点，从尾到头反过来打印链表。要求不改变链表的结构
剑指offer 6
date：2019/11/7
思路：
用栈暂存。练手用

代码：

    public void printTailToHead(Node link){
        if(link==null)
            return;
        printTailToHead(link.next);
        System.out.println(link.value);
    }