数据结构和算法-链表问题总结

发表于 | 分类于

链表翻转（Reverse Linked List）

实现翻转链表的功能

方法一：原地翻转

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
public class ReverseLinkedList {
	public ListNode reverseList(ListNode head) {
		//原地翻转法
		if(head == null) 
			return head;
		ListNode pre = null;
		ListNode cur = head;
		ListNode next = head;
		while(cur != null) {
			next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}
}  
```                           

## 方法二：建立新链表，插入式翻转  

```java    
public class ReverseLinkedList {
	public ListNode reverseList(ListNode head) {	
		//建立新链表，添加节点翻转法
		if(head == null)
			return head;
		ListNode dumpy = new ListNode(-1);
		ListNode cur = head;
		while(cur != null) {
			ListNode nex = cur.next;
			cur.next = dumpy.next;
			dumpy.next = cur;
			cur = nex;
		}
		return dumpy.next;
	}
}     
```       

# 合并两个排序的链表
**题目描述**
>输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

```java   
//递归版实现 
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}  
//非递归迭代版
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;
        }else if(list2==null){
            cur.next = list1;
        }
        return head.next;
    }
}  
```  

# 链表中倒数第k个结点

**问题描述：**   
>输入一个链表，输出该链表中倒数第k个结点。

**解题思路：快慢指针法**   
使用两个指针，fast 和 slow。 首先 fast 从链表头顺序移动 k 个节点， 将 slow 指向链表头部， 连个指针此时相差 k 个节点， 让两个指针同时移动，直到 fast 到了链表尾部，此时 slow指针所指向的节点就是链表的倒数第 k 个节点。

```java   
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k==0){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        for(int i=0; i<k-1; i++){
            fast = fast.next;
            if(fast == null){
                return null;
            }
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路：

方法一：哈希法

  • 遍历单链表的每个结点
  • 如果当前结点地址没有出现在set中，则存入set中
  • 否则，出现在set中，则当前结点就是环的入口结点
  • 整个单链表遍历完，若没出现在set中，则不存在环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null){
            return null;
        }
        HashSet<Integer> set = new HashSet<>();
        while(pHead != null){
            if(! set.contains(pHead.val)){
                set.add(pHead.val);
                pHead = pHead.next;
            }else{
                return pHead;
            }
        }
        return null;
    }
}

方法二：双指针法

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

问题描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解题思路

l1.PNG

试想一种理想情况：链表A头结点到结点8的长度与链表B头结点到结点8的长度相等，那么就可以用双指针。 

-1. 初始化：指针ta指向链表A头结点，指针tb指向链表B头结点   
-2. 如果ta == tb， 说明找到了第一个公共的头结点，直接返回即可。    
-3. 否则，ta != tb，则++ta，++tb

l2.PNG

显然图一中第一个公共结点为8，但是链表A头结点到8的长度为2，链表B头结点到8的长度为3，显然并不相等。 所以需要制造这种理想情况。

假设链表A长度为a， 链表B的长度为b，此时a != b
但是，a+b == b+a
因此，可以让a+b作为链表A的新长度，b+a作为链表B的新长度。

l3.PNG

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null || pHead2==null){
            return null;
        }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2){
            p1 = p1 == null ? pHead2 : p1.next;
            p2 = p2 == null ? pHead1 : p2.next;
        return p1;
    }
}

复杂链表的复制

题目描述:

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路：
1.png

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 RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null){
            return null;
        }
        RandomListNode pNew = pHead;
        while(pNew != null){
            RandomListNode cloneNode = new RandomListNode(pNew.label);
            RandomListNode nextNode = pNew.next;
            cloneNode.next = nextNode;
            pNew.next = cloneNode;
            pNew = nextNode;
        }
        pNew = pHead;
        while(pNew != null){
            pNew.next.random = pNew.random==null? null: pNew.random.next;
            pNew = pNew.next.next;
        }
        pNew = pHead;
        RandomListNode pClone = pHead.next;
        while(pNew != null){
            RandomListNode tempNode = pNew.next;
            pNew.next = tempNode.next;
            tempNode.next = tempNode.next==null?null:tempNode.next.next;
            pNew = pNew.next;
        }
        return pClone;
    }
}

链表中的节点每k个一组翻转

题目描述:
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 O(1)
例如：
给定的链表是1->2->3->4->5
对于 k=2, 你应该返回 2→1→4→3→5
对于 k=3, 你应该返回 3→2→1→4→5