【LeetCode】链表问题：虚拟头节点

悠悠 2022-10-29 09:11 125阅读 0赞

### 虚拟头节点 ###

*  对于有删除问题，一定要设置虚拟头节点

#### [203. 移除链表元素][203.] ####

难度简单521收藏分享切换为英文接收动态反馈

删除链表中等于给定值 \***val\*** 的所有节点。

**示例:**

输入: 1->2->6->3->4->5->6, val = 6
    输出: 1->2->3->4->5

**题解**

class Solution { 
        public ListNode removeElements(ListNode head, int val) { 
            ListNode firstNode = new ListNode();
            firstNode.next = head;
            ListNode pre = firstNode;
            ListNode node = firstNode.next;
    
            while(node != null){ 
                if(node .val == val){ 
                    pre.next = node = node.next;
                }else { 
                    pre = node ;
                    node = node.next;
                }
            }
    
            return firstNode.next;
        }
    }

#### [82. 删除排序链表中的重复元素 II][82. _ II] ####

难度中等442收藏分享切换为英文接收动态反馈

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 *没有重复出现* 的数字。

**示例 1:**

输入: 1->2->3->3->4->4->5
    输出: 1->2->5

**示例 2:**

输入: 1->1->1->2->3
    输出: 2->3

**题解**

class Solution { 
        public ListNode deleteDuplicates(ListNode head) { 
            ListNode resHead = null;
            ListNode resTail = null;
    
            ListNode node = head;
            int beforeData = Integer.MAX_VALUE;
            boolean canUseBeforeData = true;
    
            while(node != null){ 
                if(node == head){ 
                    beforeData = node.val;
                    node = node.next;
                    continue;
                }
    
                if(beforeData == node.val){ 
                    canUseBeforeData = false;
                    node = node.next;
                    continue;
                }
    
                if(canUseBeforeData){ 
                    if(resHead == null){ 
                        resHead = resTail = new ListNode(beforeData);
                    }else { 
                        resTail.next = new ListNode(beforeData);
                        resTail = resTail.next;
                    }
                }
    
                beforeData = node.val;
                canUseBeforeData = true;
                node = node.next;
            }
    
            if(canUseBeforeData && head != null){ 
                if(resHead == null){ 
                    resHead = new ListNode(beforeData);
                }else { 
                    resTail.next = new ListNode(beforeData);
                }
            }
            return resHead;
        }
    }

#### [24. 两两交换链表中的节点][24.] ####

难度中等799收藏分享切换为英文接收动态反馈

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

**你不能只是单纯的改变节点内部的值**，而是需要实际的进行节点交换。

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]

输入：head = [1,2,3,4]
    输出：[2,1,4,3]

**示例 2：**

输入：head = []
    输出：[]

**示例 3：**

输入：head = [1]
    输出：[1]

**题解**

*  对于循环中（即递推中）操作较复杂或者冗余，考虑换成递归

class Solution { 
        public ListNode swapPairs(ListNode head) { 
            ListNode firstNode = new ListNode();
            firstNode.next = head;
    
            func(firstNode);
            return firstNode.next;
        }
    
        void func(ListNode head){ 
            ListNode next = head.next;
            ListNode next2 = null;
    
            if(next != null){ 
                next2 = next.next;
            }
            if(next == null || next2 == null){ 
                return;
            }
    
            ListNode append = next2.next;
            head.next = next2;
            next2.next = next;
            next.next = append;
    
            func(next);
        }
    }

#### [25. K 个一组翻转链表][25. K] ####

难度困难881收藏分享切换为英文接收动态反馈

给你一个链表，每 *k* 个节点一组进行翻转，请你返回翻转后的链表。

*k* 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 *k* 的整数倍，那么请将最后剩余的节点保持原有顺序。

**示例：**

给你这个链表：`1->2->3->4->5`

当 *k* = 2 时，应当返回: `2->1->4->3->5`

当 *k* = 3 时，应当返回: `3->2->1->4->5`

**说明：**

*  你的算法只能使用常数的额外空间。
 *  **你不能只是单纯的改变节点内部的值**，而是需要实际进行节点交换

**题解**

class Solution { 
        public ListNode reverseKGroup(ListNode head, int k) { 
            ListNode firstNode = new ListNode();
            firstNode.next = head;
    
            func(firstNode ,k);
            return firstNode.next;
        }
    
        void func(ListNode head , int k){ 
            ListNode node = head.next;
    
            int sum = 0;
            while(node != null && sum != k){ 
                sum ++;
                node = node.next;
            }
    
            if(sum != k){ 
                return;
            }
    
            ListNode pre = null;
            ListNode cur = head.next;
            ListNode after = null;
            for(int i = 0 ; i < k ; i ++){ 
                after = cur.next;
                cur.next = pre;
                
                pre = cur;
                cur = after;
            }
    
            ListNode kLast = head.next ;
            kLast.next = cur;
            head.next = pre;
    
            func(kLast , k);
        }
    }

#### [147. 对链表进行插入排序][147.] ####

难度中等346收藏分享切换为英文接收动态反馈

对链表进行插入排序。

![20210210221644777.png][]

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。  
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

**插入排序算法：**

1.  插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2.  每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3.  重复直到所有输入数据插入完为止。

**示例 1：**

输入: 4->2->1->3
    输出: 1->2->3->4

**示例 2：**

输入: -1->5->3->4->0
    输出: -1->0->3->4->5

**题解**

class Solution { 
        public ListNode insertionSortList(ListNode head) { 
            if(head == null){ 
                return null;
            }
            
            ListNode sortArea = head;
            while(sortArea.next != null){ 
                sortArea = sortArea.next;
            }
    
            ListNode sortHead = new ListNode();
            sortHead.next = sortArea;
     
            ListNode node = head;
            while(node != sortArea){ 
                ListNode preI = sortHead;
                ListNode i = sortHead.next;
                while(i != null && node.val > i.val){ 
                    preI = i;
                    i = i.next;
                }
    
                
                ListNode next = node.next;
                preI.next = node;
                node.next = i;
    
                node = next;
            }
    
            return sortHead.next;
        }
    }

#### [19. 删除链表的倒数第 N 个结点][19. _ N] ####

难度中等1199收藏分享切换为英文接收动态反馈

给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。

\*\*进阶：\*\*你能尝试使用一趟扫描实现吗？

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]

输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]

**示例 2：**

输入：head = [1], n = 1
    输出：[]

**示例 3：**

输入：head = [1,2], n = 1
    输出：[1]

**题解**

遍历

class Solution { 
        public ListNode removeNthFromEnd(ListNode head, int n) { 
            int sum = 0;
            ListNode node = head;
    
            while(node !=  null){ 
                node = node.next;
                sum ++;
            }
    
            int idx = sum - n + 1;
            int i = 1;
    
            ListNode firstNode = new ListNode();
            firstNode.next = head;
    
            ListNode pre = firstNode;
            node = firstNode.next;
            
            while(idx != i){ 
                i ++;
                pre = node;
                node = node.next;
            }
    
            pre.next = node.next;
            return firstNode.next;
        }
    }

回溯

class Solution { 
        public ListNode removeNthFromEnd(ListNode head, int n) { 
            ListNode firstNode = new ListNode();
            firstNode.next = head;
    
            func(firstNode ,n);    
            return firstNode.next;
        }
    
        int func(ListNode head , int n){ 
            if(head.next == null){ 
                return 1;
            }
    
            int res = func(head.next ,n);
            if(res == n ){ 
                head.next = head.next.next;
            }
    
            return res + 1;
        }
        
    }

[203.]: https://leetcode-cn.com/problems/remove-linked-list-elements/
[82. _ II]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
[24.]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/cc77b5cc857942ebb69b4dbd43f2d4ce.png
[25. K]: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
[147.]: https://leetcode-cn.com/problems/insertion-sort-list/
[20210210221644777.png]: /images/20221024/a4cb1b9c18164e40a49c9bc507890183.png
[19. _ N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221024/094b5f1bf41742dca3af93082d3359ce.png