本文共 10347 字，大约阅读时间需要 34 分钟。

1. 反转链表

• 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
  

1.解题思路（迭代方法）

• 1.节点 cur、next，每次用temp先存储next.next节点；
• 2.然后改变next.next=cur，改变指针指向，由后向前；
• 3.cur=next，节点cur向后滑动；
• 4.next=temp，节点next滑动至temp处。

注意：进入while循环前，cur.next=null; 这一步不能忘！

• 时间复杂度：n；
• 空间复杂度：1.

class Solution {        public ListNode reverseList(ListNode head) {            if(head==null||head.next==null) return head;         ListNode cur=head,next=head.next;         cur.next=null; //这一步不能忘         while (next!=null){                ListNode temp = next.next;             next.next=cur;             cur=next;             next=temp;         }         return cur;     } }

2.解题思路（递归）

• 1.直接把reverseList()当为功能完备的方法，输入节点，则返回反转完成的；
• 2.那么执行reverseList(head.next)时，返回的以rec为头节点的链表，其尾节点此时就是head.next;
• 3.所以只需让head.next.next=head,让head成为尾节点；
• 4.并且再让此时的尾节点head的next变成null，head.next=null,即可。

class Solution {       public ListNode reverseList(ListNode head) {           if(head==null||head.next==null) return head;        ListNode rec = reverseList(head.next);        head.next.next=head;        head.next=null;        return rec;    }}

2.回文链表

• 请判断一个链表是否为回文链表。
• 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
  

1.解题思路（借助双向链表）

• 1.建立双向链表deque，把链表的数值依次存入deque；
• 2.for循环deque.size一般的次数，每次从deque首尾两端取出数据，进行比较；
• 3.一旦发现节点数值不同，return false；
• 4.对比结束，输出true。
• 时间复杂度：n；
• 空间复杂度：n。

class Solution {       public boolean isPalindrome(ListNode head) {           Deque
   
     deque = new LinkedList<>();        1.存入双向链表数值        while (head!=null){               deque.addLast(head.val);            head = head.next;        }        2.size一半        int sizeHalf = deque.size()/2;          for (int i = 0; i < sizeHalf; i++) {               if (deque.pollFirst()!=deque.pollLast())                return false;        }        3.到这里，说明是回文        return true;    }}
   

2.快慢指针解法

注意：0.像这种包含奇偶情况的问题，先考虑奇数情况，在考虑偶数情况，也就是在奇数情况下，小修小补，加点条件。

• 1.建立快慢指针，slow 和 fast，slow每次滑动1个节点，fast每次滑动2个节点，当fast滑动至最后时，slow刚好到中间；

• 2.在slow，fast滑动过程中，逐个反转前半部分链表，pre作为反转链表的头节点；

• 3.当fast到达最后时，开始对比：slow向后，pre向前（其实也是向pre.next的方向），依次对比值是否相同。

• 时间复杂度：n；

• 空间复杂度：1.

注意：1.你说在对比时 为什么用prepre 而非 pre？？

• 1.要注意每次while循环一次，pre与slow指向的都是同一个节点！
• 2.而且，此时的pre，它的next还是指向后边的，还没有反转从而指向前边！
• 3.在每次节点反转后，prepre都继承了pre的衣钵，所以prepre才是已经反转节点的头节点。

class Solution {       public boolean isPalindrome(ListNode head) {           if (head==null || head.next==null) return true;        ListNode slow=head,fast=head;        ListNode prepre=null,pre=head;        1.此条件说明fast到达最后，当然分别对应：偶、奇个数        while (fast!=null && fast.next!=null){               1.快慢部分            slow=slow.next;            fast=fast.next.next;            2.反转部分            ListNode temp = pre.next;            pre.next = prepre;            prepre = pre;            pre = temp;        }        2.到这里说明fast已经到达最后，可能是尾节点（奇数时） 也可能是尾节点后的null（偶数时）          奇数时，slow此时在正中间，还需要向后移动1个        if (fast!=null){                 slow=slow.next;        }        3.开始对比        你说这里为啥要用prepre而非pre？ 哈哈        while (prepre!=null){               if (prepre.val!=slow.val)                return false;            prepre=prepre.next;            slow=slow.next;        }        4.到这里说明是回文        return true;    }}

3.剑指 Offer 06. 从尾到头打印链表

• 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
  

1.思路：

• 1.使用栈，先入后出的特点；
• 2.反转链表的思路；
• 3.把链表的值，从头节点开始依次从数组末尾向前存；（需要先获取链表的长度）

仅展示思路3

class Solution {       public int[] reversePrint(ListNode head) {           if (head==null) return new int[0];        1.获取链表长度        int lenOfList=0;        ListNode temp = head;        while (temp!=null){               lenOfList++;            temp = temp.next;        }        2.建立数组        int[] res = new  int[lenOfList];        3.从尾部开始存        while (head!=null){               res[--lenOfList] = head.val;            head = head.next;        }        return res;    }}

4.剑指 Offer 25. 合并两个排序的链表

• 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
  

1.解题思路

• 1.开辟第3条链表的头节点head；
• 2.每次从两条链表上取出最大的节点接入第3条链表的尾部；
• 3.注意返回时，返回的是head.next，而非head。

class Solution {       public ListNode mergeTwoLists(ListNode l1, ListNode l2) {          1.新建第3条链表的头节点        ListNode head = new ListNode(0);        2.节点cur 进行具体的后续拼接        ListNode  cur = head;        while (l1!=null && l2!=null){           	1.拼接l1时            if (l1.val<= l2.val){                   cur.next=l1;                l1=l1.next;            }            2.拼接l2时            else {                   cur.next=l2;                l2=l2.next;            }            cur = cur.next;        }		3.拼接另一条非空串        cur.next = l1==null?l2:l1;        4.返回head的下一个节点        return head.next;    }}

5.剑指 Offer 22. 链表中倒数第k个节点

• 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

• 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

  

1.解题思路（快慢指针）

• 1.可以设置两个快慢指针，慢指针slow比快指针fast要慢k个节点；

• 2.当快指针fast到达尾部null时，慢指针slow正好是倒数第k的节点。

• 时间复杂度：n；

• 空间复杂度：1。

class Solution {       public ListNode getKthFromEnd(ListNode head, int k) {           ListNode slow = head;        ListNode fast = head;        1.fast先走k步        while (k>0){               k--;            1.1判断是否k>链表长度，即是否fast指针提前到头            if (fast==null) return fast;              fast=fast.next;        }        2.slow 和 fast 共同向后走，直到 fast为null        while (fast!=null){               fast=fast.next;            slow = slow.next;        }        3.返回slow即可        return slow;    }}

6.剑指 Offer 18. 删除链表的节点

• 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

  返回删除后的链表的头节点。

• 注意：此题对比原题有改动

1.解题思路

1.从头结点向后遍历，找到某个节点cur的值=target；

2.分两种情况：

• a：head头节点就是要删除的时；
• b：执行删除cur时，先让cur前面的节点pre.next=cur.next，然后再让cur.next=null（这步也可省略）；此顺序不可变。

class Solution {        public ListNode deleteNode(ListNode head, int val) {            if (head==null) return null;         ListNode pre = new ListNode();         ListNode cur = head;         1.当头节点就是要删除的时         if (head.val==val) return head.next;         2.当是头节点之后的节点要删除时         while (cur!=null){             	1.当节点数值不符合时             if (cur.val!=val){                	 1.1.保存cur到pre                 pre = cur;                 1.2.cur向后滑动1格                      cur = cur.next;             }             2.当节点值符合时             else {                     越过cur进行连接                 pre.next=cur.next;                 break;             }           }         return head;     }}

7.两个链表的第一个公共节点

• 输入两个链表，找出它们的第一个公共节点。
  
  

1.解题思路

• 1.2个链表第1个公共节点，是两者的内存地址相同，而不是节点数值相同；
• 2.两个头结点从各自链表从头到尾走完一遍后，再从对方链表从头到尾走一次；
• 3.有公共节点，那过程中会有headA==headB出现，如果一直没有，则最终两者共同变成null。

class Solution {       public ListNode getIntersectionNode(ListNode headA, ListNode headB) {           0.这一步其实可以省略        if (headA==null || headB==null) return null;        1.保存两个链表的头节点        ListNode hA=headA;        ListNode hB=headB;        2.只有两个头节点不是null才会继续执行        while (headA!=null || headB!=null){                1.有公共节点            if (headA==headB) return headA;            2.向后滑动，如果自己的链表走完了，则从对方的链表头开始滑动；从对方链表结束，就不会再换路径继续滑动了            headA = headA==null?hB:headA.next;            headB = headB==null?hA:headB.next;        }        3.此时说明两个链表无公共交点        return null;    }}

8.剑指 Offer 35. 复杂链表的复制

• 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null
  

1.解题思路（哈希表思路）

• 1.建立Map(旧Node,新Node)，先按节点数值val建立起一一对应的关系；
• 2.再进行连接；

class Solution {       public Node copyRandomList(Node head) {           Map
   
      map = new HashMap<>();        0.暂时性使用节点        Node cur = head;        1.先按数值一一对应存储新节点        while (cur!=null){               map.put(cur,new Node(cur.val));            cur=cur.next;        }        2.进行连接        cur=head;  再赋值为head        while (cur!=null){               Node curNew = map.get(cur);           // if (cur.next!=null)   这里不判断也行，因为如果没有，map返回就是null            curNew.next=map.get(cur.next);          //  if (cur.random!=null) 这里不判断也行，因为如果没有，map返回就是null            curNew.random=map.get(cur.random);            cur=cur.next;        }        return map.get(head);    }}
   

9.剑指 Offer 36. 二叉搜索树与双向链表

• 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
  

1.解题思路

• 1.本题是2叉搜索树，所以中序遍历（左根右），可以返回数值从小到大升序排列的节点；
• 2.然后借助队列数据结构，把节点存入队列，然后再一个个出队列，连接节点即可；
• 3.最后记得把 头节点 和尾节点之间的双向连接起来。

class Solution {       public Node treeToDoublyList(Node root) {           if (root==null) return null;        List
   
     list = new ArrayList<>();        inorder(root,list);        1.依次把头节点到尾节点之间的双向连接起来        for (int i = 0; i < list.size()-1; i++) {               list.get(i).right=list.get(i+1);            list.get(i+1).left=list.get(i);        }        2.最后把头节点 和 尾节点 连接起来        list.get(0).left=list.get(list.size()-1);        list.get(list.size()-1).right=list.get(0);        return list.get(0);    }    二叉树中序遍历    public void inorder(Node root,List
    
      list){           if (root==null) return;        inorder(root.left,list);        list.add(root);        inorder(root.right,list);    }}
    
   

2.解题思路（优化）

class Solution {       Node pre,head;    public Node treeToDoublyList(Node root) {           if (root==null) return null;        inorder(root);        head.left=pre;        pre.right=head;        return head;       }    二叉树中序遍历    public void inorder(Node root){           if (root==null) return;        inorder(root.left);        if (pre!=null) pre.right=root;        else head = root;        root.left=pre;        pre=root;        inorder(root.right);    }}

10.常用方法总结

1.链表的反转

cur：当前节点；

pre：cur的前一个节点； temp：暂时存储cur.next节点，防止链表反转后cur找不到它后边的节点；

1.ListNode temp = cur.next; 暂时存储cur.next节点2.cur.next = pre;    发生反转3.pre = cur;         反转完后，pre向后滑动4.cur = temp         cur向后滑动

2.链表的删除

cur：当前待删除结点；

pre：cur的前1个结点；

1.pre.next = cur.next;  pre.next指针越过cur节点，连接至cur的下一个节点2.cur.next=null;        cur.next设置为空，使其断开跟后边的连接（其实这一步有的时候可以没有）

2.1.链表非尾节点删除(仅知道要被删除的这个节点node)

• 1.node的数值替换为node.next节点的数值;
• 2.node.next指针直接越过原node.next指向的节点，而指向原node.next.next节点；
  (本来是删除node节点，结果狸猫换太子，node变身为它的下一个节点，并把它顶替掉)

class Solution {       public void deleteNode(ListNode node) {           node.val=node.next.val;        node.next=node.next.next;    }}

3.快慢指针的应用

3.1.fast指针比slow指针快固定的k个节点

• 可以让fast指针先后移k步，然后slow指针再动身
• head:指输入链表的头节点

ListNode slow = head;ListNode fast = head;1.fast指针先走k步while(k!=0){   	k--;	fast=fast.next;}2.fast指针与slow指针开始一起走while(fast!=null){   	fast=fast.next;	slow=slow.next;}

相关例题：

• ：输入一个链表，输出该链表中倒数第k个节点。

3.2.fast指针比slow指针快2倍

• 每次slow走1步，fast走2步；
• head:指输入链表的头节点
• while循环中多了条件：fast.next.next != null ，因为他每次走2步。

ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){   	slow = slow.next;      slow指针每次走1步	fast = fast.next.next; fast指针每次走2步}

相关例题：

• ：回文链表的判断，里边可以用它来确定链表的中间节点。(当然链表节点数目的-奇偶-也是需要考虑的问题)
• ：涉及龟兔赛跑

转载地址：http://iqqn.baihongyu.com/