算法-解决单链表问题

发表于 | 分类于 ， | | 阅读量 次
字数统计: 1k

单链表

对于单链表的操作，有很多技巧性的东西

下面我们使用六道题来以题明技巧

合并两个有序链表

力扣21：合并两个有序链表

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
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 这里使用了一个虚节点来充当头部存放节点
        ListNode virtual = new ListNode(-1);
        ListNode temp = virtual;
        ListNode l1 = list1;
        ListNode l2 = list2;
        // 这里循环退出条件是两者都不为null，因为其中只要有一者为null，A处代码就会爆空指针异常
        while (l1 != null && l2 != null) {
            // 将较小的那一个放入virtual链表中
            if (l1.val > l2.val) {// A
                temp.next = l2;
                l2 = l2.next;
            } else {
                temp.next = l1;
                l1 = l1.next;
            }
            temp = temp.next;
        }
        // 这里是为了防止出现两者长度不一致的情况，这里不需要遍历，直接将temp.next指向还不为空的那个指针
        if (l1 != null) {
            temp.next = l1;
        }
        if (l2 != null) {
            temp.next = l2;
        }
        // 最后返回虚节点的next
        return virtual.next;
    }
}

合并 k 个有序链表

力扣23：合并k个有序链表

使用一个动态数组存储所有的链表的头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode virtual = new ListNode(-1);
        ListNode temp = virtual;
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode list : lists) {
            if (list != null) {
                nodes.add(list);
            }
        }
        while (!nodes.isEmpty()) {
            nodes.sort((a, b) -> a.val - b.val);
            temp.next = nodes.get(0);
            temp = temp.next;
            if (nodes.get(0).next == null) {
                nodes.remove(0);
            } else {
                nodes.set(0, nodes.get(0).next);
            }
        }
        return virtual.next;
    }
}

单链表的倒数第 k 个节点

力扣19：删除倒数第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;
        // fast指针先走n步
        while (n-- > 0) {
            fast = fast.next;
        }
        // 如果fast变为了null说明是走到了尾部，则说明倒数第n个节点就是头结点
        // 删除头结点，那就是直接返回头结点的下一个节点作为头结点
        if (fast == null) {
            return head.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

寻找单链表的中点

力扣876：寻找单链表的中点

使用快慢指针法，slow走一步，fast走两步，当fast走到最后的时候，slow自然就在中间了

1
2
3
4
5
6
7
8
9
10
11
class Solution {
  public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

当单链表节点个数为奇数的时候，slow指向的是正中间的位置

当单链表节点个数为偶数的时候，slow指向的是中间靠右的位置

判断单链表是否包含环

力扣141：判断单链表是否成环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        if (fast == null) {
            return false;
        }
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

进阶：找到成环的起点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
   public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

判断两个单链表是否相交并找出交点

1、将第一条链表的尾部的next指向第二条链表的头部，然后返回成环的那个起点

注意：此法只是一个思路，但是力扣中这道题的校验是不允许修改原来的链表的

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
public class Solution {
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ha = headA;
        while (ha.next != null) {
            ha = ha.next;
        }
        ha.next = headB;
        return detectCycle(headA);
    }

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

2、使用技巧直接找到相交点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ha = headA;
        ListNode hb = headB;
        while (ha != hb) {
            if (ha == null) {
                ha = headB;
            } else {
                ha = ha.next;
            }
            if (hb == null) {
                hb = headA;
            } else {
                hb = hb.next;
            }
        }
        return ha;
    }
}
给作者买杯咖啡吧~~~