6.从尾到头打印链表

题目
牛客网
思路
这里提供两种解题方法：

  1. 创建一个额外的栈，然后从头到尾遍历链表，遍历的时候将遍历到的链表值存入栈中，最后再将栈中元素取出就能完成相反的顺序打印链表。
  2. 采用头插法。就是定义一个头结点，然后遍历链表，采用头插法将原链表拆除并从头部逐个插入到新链表中，遍历新链表就能得到相反顺序的元素。
    这里实现头插法：

Java

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
public class Solution {
	public ArrayList<Integer> printListFromTailToHead (ListNode listNode) {
	
		// 初始化头结点和p指针
		ListNode head = new ListNode(-1);
		ListNode p = null;
		
		// 遍历原链表并构建新链表
		while (listNode != null) {
		
			// 头插法构建新链表
			p = listNode.next;
			listNode.next = head.next;
			head.next = listNode;
			listNode = p;
			
		}
		
		// 构建列表对象
		ArrayList<Integer> printList = new ArrayList<Integer>();
		
		// 头指针指向新链表第一个值
		head = head.next;
		
		// 向列表中添加新链表各节点的值
		while (head != null) {
			printList.add(head.val);
			head = head.next;
		}
		
		// 返回列表
		return printList;
	}
}

Python3

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
class Solution:
	def printListFromTailToHead(self, listNode: ListNode) -> List[int]:
	
		# 初始化头结点
		head = ListNode(-1)
		
		while listNode is not None:
		
			# 头插法创建新链表
			p = listNode.next
			listNode.next = head.next
			head.next = listNode
			listNode = p
		
		# 初始化输出列表
		printList = []
		
		# 头结点指向新链表第一个值
		head = head.next
		
		# 将新链表的值加入到列表中
		while head is not None:
			printList.append(head.val)
			head = head.next
		
		# 返回列表
		return printList

18.2删除链表中重复的节点

题目
牛客网
思路
方法：直接比较删除
这是一个升序链表，重复的节点都连在一起，我们就可以很轻易地比较到重复的节点，然后将所有的连续相同的节点都跳过，连接不相同的第一个节点。

复杂度分析：

  • 时间复杂度：O(n)，其中n为链表节点数，只有一次遍历
  • 空间复杂度：O(1)，只开辟了临时指针，常数级空间
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
38
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {

				// 空链表
        if (pHead == null) {
            return null;
        }
        
        // 在链表前加一个表头
        ListNode res = new ListNode(0);
        res.next = pHead;
        
        ListNode q = res;
        
        while ((q.next != null) && (q.next.next != null)) {
        
        		// 遇到相邻两个节点值相同
            if (q.next.val == q.next.next.val) {
                int temp = q.next.val;
                
                // 将所有相同的都跳过
                while ((q.next != null) && (q.next.val == temp)) {
                    q.next = q.next.next;
                }
                
            }
            else {
                q = q.next;
                
            }
        }
        
        // 返回时去掉表头
        return res.next;
        
        
    }
}

22.链表中倒数第K个节点

题目
牛客网
思路
方法：快慢双指针
第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。

复杂度分析：

  • 时间复杂度：O(n)，总共遍历n个链表元素
  • 空间复杂度：O(1)，常数级指针变量，无额外辅助空间使用
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
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {

				// 初始化快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        
        // 快指针先行k步
        for (int i = 0;i < k;i++) {
            
            if (fast != null) {
                fast = fast.next;
            }
            // 达不到k步说明链表过短，没有倒数k
            else {
                return null;
            }

        }
        
        // 快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        return slow;
    }
}

23.链表中环的入口节点

题目
牛客网
思路
方法：双指针
根据题干，不说别的，我们能发现这道题需要完成两个任务：

  1. 判断链表是否有环。
  2. 在有环的链表中找到环的入口。

那我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了n圈，慢指针在环中走了m圈，它们才相遇，而进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。快指针一共走了x+n(y+z)+y步，慢指针一共走了x+m(y+z)+y，这个时候快指针走的倍数是慢指针的两倍，则x+n(y+z)+y=2(x+m(y+z)+y)，这时候x+y=(n−2m)(y+z)，因为环的大小是y+z，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这y个节点，那说明这y个节点它们就是重叠遍历的，那它们从入口位置就相遇了，这我们不就找到了吗？

时间复杂度分析：

  • 时间复杂度：O(n)，最坏情况下遍历链表两次
  • 空间复杂度：O(1)，使用了常数个指针，没有额外辅助空间

注：以上描述了以fast比slow超过一个环为例描述了这个过程，经过推算，超过多个环和超过一个环的规律是一样的都是当fast重头开始，slow从相遇点开始顺时针遍历，两者以相同的速度会在环口相遇。

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
38
39
40
41
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        
        if (pHead == null) {
            return null;
        }
        
        // 定义快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        
        while ((fast != null) && (fast.next != null)) {
        
        		// 快指针是慢指针的两倍速度
            fast = fast.next.next;
            slow = slow.next;
            
            // 记录快慢指针第一次相遇的结点
            if (fast == slow) {
                break;
            }
        }
        
        // 若是快指针指向null，则不存在环
        if ((fast == null) || (fast.next == null)) {
            return null;
        }
        
        // 重新指向链表头部
        fast = pHead;
        
        // 与第一次相遇的结点相同速度出发，相遇结点为入口结点
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        
        return fast;
    }
}

24.反转链表

题目
牛客网
思路
方法：头插法

时间复杂度分析：

  • 时间复杂度：O(n)，遍历一次链表
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode ReverseList(ListNode head) {
    
    		// 初始化头结点
        ListNode newList = new ListNode(-1);
        
        while (head != null) {
        
        		// 头插法新建链表操作
            ListNode next = head.next;
            head.next = newList.next;
            newList.next = head;
            head = next;
        }
        
        return newList.next;
    }
}

25.合并两个排序的链表

题目
牛客网
思路
方法：迭代归并

复杂度分析：

  • 时间复杂度：O(m+n),m，n分别为两个单链表的长度
  • 空间复杂度：O(1)
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
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
    
    		// 初始化头结点
        ListNode head = new ListNode(-1);
        
        // 初始化遍历指针
        ListNode cur = head;
        
        while ((list1 != null) && (list2 != null)) {
            
            // 遍历指针的下个值指向值更小节点，并且对应链表指针后移
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            }
            else {
                cur.next = list2;
                list2 = list2.next;
            }
            
            // 遍历指针后移
            cur = cur.next;
        }
        
        // 其中一个链表遍历结束后链接下个链表剩余的所有节点
        if (list1 == null) {
            cur.next = list2;
        }
        if (list2 == null) {
            cur.next = list1;
        }
        
        return head.next;
    }
}

35.复杂链表的复制

题目
牛客网
复杂度分析：

  • 时间复杂度：O(n)，其中n为链表长度，遍历三次链表，第一次遍历n个节点，第二次、第三次遍历2n个节点
  • 空间复杂度：O(1)，常数级变量，无额外辅助空间
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
38
39
40
41
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
    
        if (pHead == null) {
            return null;
        }
        
        // 插入新节点并串联
        RandomListNode cur = pHead;
        while (cur != null) {
            RandomListNode clone = new RandomListNode(cur.label);
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }
        
        // 建立random链接
        cur = pHead;
        while (cur != null) {
            RandomListNode clone = cur.next;
            
            if (cur.random != null) {
                clone.random = cur.random.next;
            }
            
            cur = clone.next;
        }
        
        // 拆分
        cur = pHead;
        RandomListNode pCloneHead = cur.next;
        while (cur.next != null) {
        
            RandomListNode next = cur.next;
            cur.next = next.next;
            cur = next;
        }
        
        return pCloneHead;
    }
}

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

题目
牛客网
思路：
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
复杂度分析：

  • 时间复杂度：O(m+n), m，n分别为链表A，B的长度，最坏情况下，公共结点为最后一个，需要遍历m+n个结点
  • 空间复杂度：O(1)
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
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    
    		// 初始化两个用于遍历的头结点
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        
        while (l1 != l2) {
            
            // 判断l1的遍历方向
            if (l1 == null) {
                l1 = pHead2;
            }
            else {
                l1 = l1.next;
            }
            
            // 判断l2的遍历方向
            if (l2 == null) {
                l2 = pHead1;
            }
            else {
                l2 = l2.next;
            }

        }
        
        return l1;
    }
}