单链表初阶的两道基础题

注意！！！

学习的是解题的思维！

翻转单链表（链接在末尾）

解题思路

如果给你一个1->2->3->4->5->null的链表，你需要将他改为5->4->3->2->1->null

迭代解法

我们先看图理解一下

• 在第一步：我们要做的是将cur.next指向prev，但是当我的cur.next指向prev时就找不到了下一个结点。
• 第二步：所以我们需要再定义一个指针去存储cur的下一个结点curNext=cur.next，保存下一个结点后，我们就可以让cur.next=prev了，接下来呢？
• 第三步：我们需要做的就是让cur向右移，再让cur的next指向1这个结点，那么我们如何找到1这个结点呢？可以看到，我们的cur.next=null时，我们的cur正好是1这个结点，所以呢？我们就可以将cur赋值给prev:prev=cur,这样我们的prev就是1这个结点了（蓝框上部分）。
• 第四步：因为curNext指针存了下一个结点的地址，所以我们可以直接让cur=curNext,这样我们的cur就是下一个结点了，经过这个操作之后再将curNext置为cur的后一个结点，也就是curNext=cur.next
• 最后如蓝色框上部分

如果还有疑问，那就看下图

在遍历链表时，将当前节点的 cur.next 指针改为指向前一个节点。由于找不到前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

代码如下

class Solution {
    public ListNode reverseList(ListNode head) {
        //没有结点或者只有一个结点不需要逆置
        if (head==null||head.next==null) {
            return head;
        }
        ListNode prev=null;//记录前一个节点
        ListNode cur=head;//记录当前结点
        while (cur!=null) {
       	   //记录后一个结点
            ListNode curNext=cur.next;
            cur.next=prev;//当前结点的next指向前一个节点
            prev=cur;//将前一个结点移动到当前结点
            cur=curNext;//当前结点移动到下一个结点
        }
        //最后返回头节点
        return prev;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析：

• 时间复杂度O(n),其中 N 是给定链表中的结点数目。
• 空间复杂度O(1)

链表的倒数第K个结点（链接在末尾）

普通解法

很显然，求倒数第k个，可以转换成求正数第多少个呢？

我们来看图

我们总共有五个结点，如果需要找到倒数第3个，那就是正数第二个，也就是正数第n-k个，n为链表长度。

• 第一步：遍历链表记录链表的长度
• 第二步：用链表长度减去k，也就是n-k,求出正数第几位
• 第三步：再次遍历链表，当循环n-k次后退出循环并返回

如图：

第一遍遍历

第二遍遍历

有了上面的过程，还需要考虑2个细节

• k<=0 或者头结点最开始就为空，也就是没有节点
• 节点的总个数 < K

代码如下

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    //判断链表是不是为空，并且k不能小于等于0
        if (k<=0||head==null) {
            return null;
        }
        int n=0;//记录链表长度
        ListNode cur=head;
        while (cur!=null) {
            cur=cur.next;
            n++;
        }
        //当我的链表长度小于K说明K不在链表里面
        if(n<k) {
            return null;
        }
        cur=head;
        int size=n-k;//循环size次
        while(size>0) {
                cur=cur.next;
                size--;
        }
        return cur;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

n为链表的总长度，如果k总是在倒数第一个节点，那么此方法需要遍历链表2次，最坏时间复杂度为O(2*n)

复杂度分析：

• 时间复杂度O(2*n) 其中 N 是给定链表中的结点数目。
• 空间复杂度O(1)

进阶解法

定义一个快慢指针，先让快指针走K步，然后慢指针和快指针一起走，当快指针为null时，我们的慢指针就是倒数第K个数。

究竟上面的原理是如何推理出来的呢？

我们看图演示

第一步：先让快指针cur走K步，如图二
第二步：快指针，慢指针一起走，当快指针为null时退出循环
第三步：此时prev就是倒数第K个结点，返回prev就行

具体过程如下

使用如图的快慢指针，首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点

代码入下
注意注释！！！

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
		 //判断链表是不是为空，并且k不能小于等于0	
        if (k<=0||head==null) {
            return null;
        }
        int n=0;
        ListNode prev=head;
        ListNode cur=head;
        while (n<k) {
        //判断cur是否为null
        //如果为null返回null
            if (cur==null) {
               return null;
            }
            cur=cur.next;
            n++;
            //如果将if放到下面，
            //那么判断倒数第n个结点时就会出错，n是链表长度，
            //也就是查找链表头节点时会报错
            //if (cur==null) {
            // return null;
            // }
        }
        while (cur!=null) {
            prev=prev.next;
            cur=cur.next;
        }
        return prev;
    }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

作者总结：

有一个极端条件就是当倒数第K个结点是头节点时，不能将if放到我在代码注释的那个位置，如下图

如果在下面判断当cur == null时就退出，那么存在一种情况就是当我的cur==null时，我的prev就是倒数第5个结点符合条件，如果此时退出结果就会和预期结果不一样，所以我们将判断的条件写在了上面，那样的话，只有当我们的n没有符合条件时并且cur==null，才返回null,这样就避免了上面的错误

反转一个单链表：oj题

输入一个链表，输出该链表中倒数第k个结点oj题

下期预告：合并两个有序链表，判断回文链表，链表的相交结点