LeetCode初级算法-链表篇

题目连接

这7道题，包含了链表的增删查改

链表有一个坑爹的地方就是不知道链表的长度

删除链表相关

删除链表一般要在头节点处添加一个哑巴节点。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部

1. 删除链表中的节点

这个题主要是让我熟悉LeetCode里面的链表怎么用，这其实算是一个阅读理解题。。。

public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; }

2. 删除链表的倒数第N个节点

这个题正常来说是两种方法

第一种方法比较好容易想到，即先遍历一遍算出链表的长度，第二次遍历删除需要删除的节点：

时间复杂度为O(N), 空间复杂度为O(1)

public ListNode removeNthFromEnd(ListNode head, int n) { // 哑巴节点 防止链表出现单个元素 ListNode dummy = new ListNode(0); dummy.next = head; int length = 0; ListNode tempHead = head; // 计算长度 for(; tempHead != null; length ++) tempHead = tempHead.next; tempHead = dummy; for(int i = 0; i < length - n; i ++) tempHead = tempHead.next; tempHead.next = tempHead.next.next; return dummy.next; }

第二种方法是采用双指针，一次遍历即删除所要求的的节点

时间复杂度为O(N), 空间复杂度为O(1)

以1,2,3,4,5为例：

其中，这两个指针相隔n个节点。tempHeadI在链表左边，tempHeadJ在链表右边。我们会发现，当tempHeadJ达到最后一个节点的next，即为null之后，我们可以发现，左边的tempHeadI就在要删除的第n个节点前面，这样就可以完成删除了。

public ListNode removeNthFromEnd(ListNode head, int n) { // 防止链表出现单个元素 ListNode dummy = new ListNode(0); dummy.next = head; ListNode tempHeadI = dummy; ListNode tempHeadJ = dummy; for (int i = 0; tempHeadJ != null; i ++, tempHeadJ = tempHeadJ.next) if (i > n) tempHeadI = tempHeadI.next; tempHeadI.next = tempHeadI.next.next; return dummy.next; }

修改链表相关

3. 反转链表

这种题可以用递归或者迭代解决

采用迭代，分为两种情况

当所给链表小于两个节点时，直接返回；否则如下图所示：

public ListNode reverseList(ListNode head) { ListNode i = head; if (i == null) return null; ListNode j = head.next; if (j == null) return i; ListNode k = head.next.next; head.next = null; while (true) { j.next = i; if (k == null) return j; i = k.next; k.next = j; if (i == null) return k; j = i.next; i.next = k; if (j == null) return i; k = j.next; } 采用递归解决

我们需要注意的是要设置一个全局变量，来作为要返回值的头结点

ListNode tempHead = null; public ListNode reverseList(ListNode head) { if (head == null) return null; getNextNode(head).next = null; return tempHead; } private ListNode getNextNode(ListNode node) { if (node.next == null) { tempHead = node; return node; } ListNode ret = getNextNode(node.next); ret.next = node; return node; }

增加链表相关

4. 合并两个有序链表

这个题算是除了第一题之外最简单的题了，按照自己的思路走就能做对。

有两种方法：

新开一个链表，然后比较l2和l1，谁的节点元素小，就把谁的节点加入到新开的链表里面

第二种方法，不新开链表，让返回值的头节点指向l2和l1中第一个节点元素的比较小的那个链表

要注意几点：

l1或者l2为空的情况谁第一的节点最小，用谁作为头结点一长一短的情况 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode tempSmall = null; ListNode tempBig = null; if (l1.val > l2.val) { tempSmall = l2; tempBig = l1; } else { tempSmall = l1; tempBig = l2; } ListNode head = tempSmall; while (tempSmall.next != null && tempBig != null) { if (tempBig.val >= tempSmall.val && (tempSmall.next == null || tempSmall.next.val >= tempBig.val)) { ListNode temp = tempBig; tempBig = tempBig.next; temp.next = tempSmall.next; tempSmall.next = temp; } tempSmall = tempSmall.next; } if (tempBig != null) tempSmall.next = tempBig; return head; }

查看链表相关

5.回文链表

第一个方法，新建一个链表，把原来链表翻转过来，然后比较，如果两个链表相同，则是回文链表

第二个方法，把链表的值放到数组里，然后通过数组来观察是否是回文数组。空间O(n)，时间O(n)

public boolean isPalindrome(ListNode head) { int length = 0; ListNode temp = head; for (; temp != null; temp = temp.next, length ++); int[] arrs = new int[length]; for (int i = 0; head != null; head = head.next, i ++) arrs[i] = head.val; for(int i = 0; i < length / 2; i ++) if (arrs[i] != arrs[length - i - 1]) return false; return true; }

第三个方法，就是题目上要求的O(1)的空间复杂度和O(n)的时间复杂度

这个方法也是对第一个方法的优化：‘

只翻转后半部分：定义两个指针i和j，i走一步，j走两步，当j到达末尾时，i刚好到达中间之后，翻转后半部分的链表（此时只新建了一个节点，二第一种方法是新建了n个节点）最后，比较即可 ListNode turnHead = null; public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head; ListNode fast = head; // 找到中间的节点 while(fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } slow = slow.next; // 把turnHead指向slow翻转后的值 getNextNode(slow).next = null; // 比较 while (turnHead != null) { if (turnHead.val != head.val) return false; turnHead = turnHead.next; head = head.next; } return true; } private ListNode getNextNode(ListNode node) { if (node.next == null) { turnHead = node; return node; } ListNode ret = getNextNode(node.next); ret.next = node; return node; }

6. 环形链表

两种方法：

第一种比较容易想到，用hash产生映射，不过这种方法的空间复杂度是O(n)

public boolean hasCycle(ListNode head) { Set<ListNode> hash = new HashSet<>(); for(;head != null; head = head.next) if (hash.contains(head)) return true; else hash.add(head); return false; }

第二种方法，还是双指针，一个快指针，一个慢指针，入过快指针追上慢指针，则说明是一个环形链表。这个空间复杂度是O(1)

public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; for (ListNode slow = head, fast = head.next; fast != slow; fast = fast.next.next, slow = slow.next) if (fast.next == null || fast.next.next == null) return false; return true; }