最近在刷leetcode上关于链表的一些高频题,在写代码的过程中总结了链表的一些解题技巧和常见题型。
结点的删除
指定链表中的某个结点,将其从链表中删除。
由于在链表中删除某个结点需要找到该结点的前一个位置,然后将前一个结点的next指针直接绕过该结点即可删除。但找到该结点的前一个位置需要指针遍历,其实还有一种更简单的trick,就是将要删除的结点的值设为该结点的后一个的值,然后删除该结点的后一个结点(间接删除,不需要找遍历前一个指针),代码如下:
1 2 3 4 5 6
| class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } }
|
在表头前增加虚拟结点
很多场合下,在链表的表头前增加一个虚拟结点(dummy),并让其指向head,能简化很多操作。如在新创建一个链表或对链表进行遍历操作时,如果不增加虚拟结点,就需要处理当前结点是头结点的特殊情况(因为头结点前没有其他结点,导致操作代码不一致)。加了虚拟结点后就可以像操作其他结点一样对待头结点了,最后只需要返回虚拟结点的next就可以了。
如LeetCode上的这一题: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 20
| class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode p = dummy; ListNode q = dummy; while(n > 0) { q = q.next; n--; } while(q.next != null) { p = p.next; q = q.next; } p.next = p.next.next; return dummy.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
| class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; while(head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } public ListNode reverseList2(ListNode head) { if(head == null || head.next == null) return head; ListNode next = head.next; ListNode newHead = reverseList(next); next.next = head; head.next = null; return newHead; } }
|
快慢双指针
有时候需要找到链表的中间位置的结点,这时就需要设置两个指针slow和fast,slow每次往前移动一个,fast移动两个。当fast为空时,slow就指向了链表的中间位置。比如leetcode上的Palindrome 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
| class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) { return true; } ListNode fast = head, slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } slow = reverseList(slow); while(head != null && slow != null) { if(head.val != slow.val) { return false; } head = head.next; slow = slow.next; } return true; } private ListNode reverseList(ListNode head) { ListNode prev = null; while(head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } }
|
合并两个有序链表
这也是碰到的很常见的问题了,合并两个有序链表使其仍然保持有序,一般采用双指针法,这也需要能够熟练地写出无bug的代码来。这里给出迭代和递归两种实现方式:
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
| class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null && l2 == null) { return null; } ListNode p = l1; ListNode q = l2; ListNode dummy = new ListNode(0); ListNode pp = dummy; while(p != null && q != null) { if(p.val < q.val) { dummy.next = new ListNode(p.val); p = p.next; } else { dummy.next = new ListNode(q.val); q = q.next; } dummy = dummy.next; } if(p != null) { dummy.next = p; } if(q != null) { dummy.next = q; } return pp.next; } public ListNode mergeTwoLists2(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; } } }
|
目前碰到的问题就这么多了,后面再继续补充吧。