剑指offer链表篇

从尾到头打印链表

题目链接:从头到尾打印链表信息

题目分析:

• 直接遍历借助栈数据结构先进先出

题目解答:

空间/时间复杂度:O(n)

java

import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        if(listNode==null||listNode.next==null) return res;
        while(listNode!=null){ //栈保存
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.isEmpty()){//然后出栈!
            res.add(stack.pop());
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

python

class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        # write code here
        res = []
        cur = listNode
        while cur != None:
            res.insert(0,cur.val)
            cur = cur.next
        return res
1
2
3
4
5
6
7
8
9

• 我们可以这里关键点就是需要知道当前节点上一个节点的位置!
• 这里我们可以通过递归,可以达到和栈一样的效果!

复杂度和上面一样,就是通过递归栈代替了我们自定义的栈!

java

import java.util.ArrayList;
public class Solution {
     ArrayList<Integer> res;
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //递归!!!
       res = new ArrayList<>();
        dfs(listNode);
        return res;
    }
    public void dfs(ListNode cur){
        if(cur==null) return;
        dfs(cur.next);//找尾!
        res.add(cur.val);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

python

import sys
sys.setrecursionlimit(100000) # 设置递归深度!

class Solution:
    def dfs(self,cur: ListNode, res: List[int]):
        if cur is None:
            return
        self.dfs(cur.next,res)
        res.append(cur.val)

    def printListFromTailToHead(self, listNode: ListNode) -> List[int]:
        # write code here
        res = []
        self.dfs(listNode, res)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

反转链表

题目链接:反转链表

题目分析:

• 这里空间复杂度为O(1)那就要求原地反转链表!
• 显然这里不能借助其他数据结果,或者递归!
• 所以我们可以通过多个指针记录反转节点位置进行操作

java

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null,cur = head,end = head;
        while(end!=null){
            end = cur.next;
            cur.next = pre;
            pre = cur;
            cur = end;
        }
        return pre;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

python

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        pre,cur,end = None,head,head
        while cur != None:
            end = cur.next
            cur.next = pre
            pre = cur
            cur = end
        return pre
1
2
3
4
5
6
7
8
9
10

合并两个排序的链表

题目链接:合并两个排序的链表

题目分析:

• 这里是2个排序链表!
• 我们可以创建一个新链表,然后遍历这2个链表,比较2个链表中的元素!
• 较小值就尾插到新链表!
• 返回新链表即可
• 注意比较时有可能有链表已经为空,所以直接尾插另一个链表即可!

java

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode cur1 = list1,cur2 = list2;
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<cur2.val){
                cur.next = cur1;
                cur1 = cur1.next; 
            }else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
		if(cur1!=null){
			cur.next = cur1;
		}
		if(cur2!=null){
			cur.next = cur2;
		}
		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

python

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        dummy = ListNode(-1)
        cur = dummy
        while pHead1 and pHead2:
            if pHead1.val<pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next
 		if pHead1:
            cur.next = pHead1
        if pHead2:
            cur.next = pHead2
        return dummy.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

两个链表的第一个公共结点

题目链接: 两个链表的第一个公共结点

题目分析:

• 可以直接先遍历一遍计算2个链表长度的差值,然后再让一个链表遍历到差值位,然后同时遍历,比较节点是否相同!!!
• 通过两个指针速度相同,走过的路程相同必会相遇!
• cur1 走完 L1,cur1指向 L2,cur2走完L2,指向L1!

差值法
java

//先计算长度差,然后让一个指针先走差值单位!
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            ListNode cur1 = pHead1;
            ListNode cur2 = pHead2;
        int size1 = 0;
        int size2 = 0;
        while(cur1!=null){
            cur1 = cur1.next;
            size1++;
        }
        while(cur2!=null){
            cur2 = cur2.next;
            size2++;
        }
        if(size1>size2){
            int len = size1 - size2;
            while(len-->0){
                pHead1 = pHead1.next;
            }
        }else{
             int len = size2 - size1;
            while(len-->0){
                pHead2 = pHead2.next;
            }
        }
         
        while(pHead1!=null){
            if(pHead1.val==pHead2.val){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
}
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
32
33
34
35
36
37

python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        len1=len2 = 0
        cur1,cur2 = pHead1,pHead2
        while cur1:
            len1+=1
            cur1 = cur1.next
        while cur2:
            len2 +=1
            cur2 = cur2.next
        # 这里还要判断那个链表的长度更长...
        # 我们默认设置为cur1链表更长!
        size = 0
        if len1>len2:
            size = len1 - len2
            cur1 = pHead1
            cur2 = pHead2
        else:
            size = len2 - len1
            cur1 = pHead2
            cur2 = pHead1
        while size:
            cur1 = cur1.next
            size -= 1
        #遍历2个链表比较!
        while cur1 and cur2:
            if cur1 == cur2:
                return cur1
            cur1 = cur1.next
            cur2 = cur2.next
        return cur1

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
32
33

相同路程法
操作如图所示

java

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            //定义2个指针! 
            // cur1 走完 L1,又从 L2开始!
            // cur2 走完 L2,又从 L1开始!
            // 这里两个指针速度相同,走过的长度相等,如果有相同节点肯定相遇!
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1!=cur2){//不存在公共节点,两个指针会来到null相等退出循环!
            cur1 = (cur1==null) ? pHead2 : cur1.next;
            cur2 = (cur2 == null) ? pHead1 : cur2.next;
        }
        return cur1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        a = pHead1
        b = pHead2
        while a!=b:
            a = a.next if a else pHead2
            b = b.next if b else pHead1
        return a 
1
2
3
4
5
6
7
8
9

链表中环的入口结点

题目链接: 链表中环的入口结点

题目分析:

• 可以通过哈希表保存节点,然后遇到重复节点,就是环入口节点,但是这里要求空间复杂度为O(n),所以并不行…
• 我们可以通过快慢指针!先找到快慢指针的相遇位置,有环必相遇.fast走2步,slow走1步!
• 找到相遇点后,然后让一个指针从头节点出发,另一个节点在相遇位置出发,他们相遇点就是环入口!
  

题目解答:
java

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //快慢指针,利用链表头到入口距离 = 相遇点到入口距离!
        //所以当两个节点相遇后再走L距离就是入口位置!
        //相遇后让其中一个指针从链头开始走L,一个从相遇点开始!
        ListNode slow = pHead,fast = pHead;
        while(fast!=null&&fast.next!=null){//注意判断条件!!!!
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                //相遇!
                //让slow从头结点开始!
                slow = pHead;
                while(fast!=slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}
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
32
33
34

python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        fast = slow = pHead
        # 快慢指针!
        # fast走的路程是slow的2倍,设圆弧长:C,头节点到环入口为:L,相遇点理入口环距离:X
        # 根据路程关系: L+C+X = 2*(L+X) -> L+C+X = 2L+2X  C = L+X -> L = C-X
        # 所以相遇点到环入口等于L长度!
        while fast!=None and fast.next!=None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                # 相遇!
                fast = pHead
                while fast!=slow:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None
            
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

链表中倒数最后k个结点

题目链接: 链表中倒数最后k个结点

题目分析:

• 遍历拿到数组长度,再次遍历size-k返回即可!
• 我们可以通过双指针,让fast先走k个节点,slow指针再开始出发,当fast走完,slow就到了倒数第k个节点位置!

 public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        int size = 0;
        ListNode cur = pHead;
        while(cur!=null){
            cur = cur.next;
            size++;
        }
        if(size<k){
            return null;
        }
        int n = size - k;
        while(n-->0){
            pHead = pHead.next;
        }
        return pHead;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

python

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        # 判断是否有倒数第k个节点!
        size = 0
        cur = pHead
        while cur:
            size +=1
            cur = cur.next
        #不存在倒数第k个节点!
        if size <k:
            return None
        # 遍历!
        n = size -k
        cur = pHead
        while n:
            cur = cur.next
            n -=1
        return cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双指针
java

 public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode slow = pHead,fast = pHead;
        while(k-->0){
            if(fast ==null)
                return null;
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

python

def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        fast = slow = pHead
        while k:
            if fast == None:
                return None
            fast = fast.next
            k-=1
        while fast:
            fast = fast.next
            slow = slow.next
        return slow
1
2
3
4
5
6
7
8
9
10
11
12

复杂链表的复制

题目链接:复杂链表的复制

题目分析:

• 这里需要浅拷贝,我们可以遍历整个链表通过哈希表保存当前节点和random的映射关系,就是复制好所有的random节点,由此也就复制了所有链表的节点,然后我们需要做的就是再次遍历链表,然后把链表的连接连上即可!
  

java

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null) return null;
        //保存节点和random节点的映射关系!
        //并且先创建部分链表,除了随机指针!
        Map<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        while(cur!=null){
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next; 
        }
        //复制!
        cur = pHead;
        while(cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

python

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        cur = pHead
        table = {}
        if pHead == None:
            return None
        # 获取映射关系
        while cur:
            table[cur] = RandomListNode(cur.label)
            cur = cur.next
        #进行连接!
        cur = pHead
        while cur:
            table[cur].next = table.get(cur.next)
            table[cur].random = table.get(cur.random)
            cur = cur.next
        return table[pHead]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除链表中重复的结点

题目链接:删除链表中重复的结点

题目分析:

• 这里要求时间复杂度和空间复杂度都是O(n),所以这里的方法有很多!
• 可以借助其他数据结构进行去重,然后再次进行链接,返回头结点即可!
• 我们这里通过指针进行遍历原地去重,因为这里结点有序!
  

java

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null||pHead.next==null) return null;
        ListNode res = new ListNode(-1);
        res.next = pHead;
        ListNode cur = res;
        while(cur.next!=null&&cur.next.next!=null){
            //遇到相邻两个节点值相同直接删除!
            if(cur.next.val==cur.next.next.val){
                int tmp = cur.next.val;
                //跳过!
                while(cur.next!=null&&cur.next.val==tmp){
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return res.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

python

class Solution:
    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        # write code here
        res = ListNode(-1)
        res.next = pHead
        cur = res
        while cur.next!=None and cur.next.next!=None:
            if cur.next.val==cur.next.next.val:
                #去重!
                val = cur.next.val
                while cur.next!=None and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return res.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

删除链表的节点

题目链接:删除链表的节点

题目分析:

• 这就是简单的删除节点!我们只需要遍历,然后找到该节点进行删除即可!

java

 public ListNode deleteNode (ListNode head, int val) {
        // write code here
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while(cur.next!=null){
            if(cur.next.val==val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

python

class Solution:
    def deleteNode(self , head: ListNode, val: int) -> ListNode:
        # write code here
        res = ListNode(-1)
        res.next = head
        cur = res
        while cur.next:
            if cur.next.val==val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return res.next
1
2
3
4
5
6
7
8
9
10
11
12