0%

数据结构与算法之美(三):写出正确的链表代码

1. 单链表反转

  • 题目:LeetCode-206: Reverse Linked List

  • 写法一:迭代版

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class solution {
    public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;

    while(cur != null) {
    next = cur.next;
    cur.next = pre; // 从前往后
    pre = cur;
    cur = next;
    }
    return pre;
    }
    }
  • 写法二:递归版

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class solution {
    public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) {
    return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head; // 从后往前
    head.next = null;
    return newHead;
    }
    }

2. 链表中环的检测

  • 题目:LeetCode-141: Linked List Cycle

  • 写法一:哈希表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<ListNode> ();
    while(head != null) {
    if(nodesSeen.contains(head)) {
    retrun true;
    } else {
    nodesSeen.add(head);
    }
    head = head.next;
    }
    return false;
    }
    }
  • 写法二:双指针

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

    while(slow != fast) {
    if(fast == null || fast.next == null) {
    return false;
    }
    slow = slow.next;
    fast = fast.next.next;
    }
    retrun true;
    }
    }

3. 两个有序的链表合并

  • 题目:LeetCode-21: Merge Two Sorted Lists

  • 写法一:一般写法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(-1);
    ListNode current = result;

    while(l1 != null && l2 != null) {
    if(l1.val < l2.val) {
    current.next = l1;
    l1 = l1.next;
    } else {
    current.next = l2;
    l2 = l2.next;
    }
    current = current.next;
    }
    current.next = (l1 != null) ? l1 : l2;
    return result.next;
    }
    }
  • 写法二:递归版本1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    if(l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
    } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
    }
    }
    }
  • 写法三:递归版本2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null) return l2;
    if(l2 == null) return l1;
    ListNode head = (l1.val < l2.val) ? l1 : l2;
    ListNode nonhead = (l1.val < l2.val) ? l2 : l1;
    head.next = mergeTwoLists(head.next, nonhead);
    return head;
    }
    }

4. 删除链表倒数第 n 个结点

  • 题目:LeetCode-19: Remove Nth Node From End of List

  • 写法:双指针

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode left = dummy;
    ListNode right = dummy;

    for(int i=1; i<=n+1; i++) {
    right = right.next;
    }

    while(right != null) {
    right = right.next;
    left = left.next;
    }
    left.next = left.next.next;
    return dummy.next;
    }
    }

5. 求链表的中间结点

  • 题目:LeetCode-876: Middle of the Linked List

  • 写法:快慢指针

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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;
    }
    }
-------------------- 本文结束感谢您的阅读 --------------------