【LeetCode】链表问题：典型操作

àì夳堔傛蜴生んèń 2022-10-29 09:11 132阅读 0赞

### 反转链表 ###

*  时间复杂度 O(n) ，定义三个指针
    
        ListNode pre = null , cur = head , after = null;
        
        while(...){ 
            after = cur.next;
            cur.next = pre;
            pre = cur;
            cur = after;
            ...
        }

#### [206. 反转链表][206.] ####

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

反转一个单链表。

**示例:**

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

**题解**

#### [92. 反转链表 II][92. _ II] ####

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

反转从位置 *m* 到 *n* 的链表。请使用一趟扫描完成反转。

**说明:**  
1 ≤ *m* ≤ *n* ≤ 链表长度。

**示例:**

输入: 1->2->3->4->5->NULL, m = 2, n = 4
    输出: 1->4->3->2->5->NULL

**题解**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
    class Solution { 
        public ListNode reverseBetween(ListNode head, int m, int n) { 
            int idx =  1;
            ListNode pre = null;
            ListNode cur = head;
            ListNode after = cur.next;
    
            while(idx < m){ 
                pre = cur;
                cur = cur.next;
                idx ++;
            }
    
            ListNode target1 = pre;
            ListNode target2 = cur;
    
            while(idx <= n){ 
                after = cur.next;
                cur.next = pre;
                pre = cur;
                cur = after;
                idx ++;
            }
    
            if(target1 == null){ 
                head = pre;
            }else { 
                target1.next = pre;
            }
            target2.next = cur;
    
            
            return head;
        }
    }

### 基操 ###

*  对于多数链表题来说，直接再开辟一个链表空间最简单
 *  注意：凡是要把一个节点移动到其他位置，一定要改该节点前面的 next （所以说如果有要移动的情况，那么一定是前后指针遍历）
 *  注意：如果把某个节点移到尾节点了，那么一定改该节点 next 为 null。

#### [86. 分隔链表][86.] ####

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

给你一个链表和一个特定值 `x` ，请你对链表进行分隔，使得所有小于 `x` 的节点都出现在大于或等于 `x` 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

**示例：**

输入：head = 1->4->3->2->5->2, x = 3
    输出：1->2->2->4->3->5

**示例**

class Solution { 
        public ListNode partition(ListNode head, int x) { 
            ListNode smallerListHead  = null;
            ListNode smallerListTail = null;
    
            ListNode BiggerListHead = null;
            ListNode BiggerListTail = null;
    
            ListNode node = head;
            while(node != null){ 
                if(node.val < x){ 
                    if(smallerListHead == null){ 
                        smallerListHead = new ListNode(node.val);
                        smallerListTail = smallerListHead;
                    }else { 
                        smallerListTail.next = new ListNode(node.val);
                        smallerListTail = smallerListTail.next;
                    }
                }else { 
                    if(BiggerListHead == null){ 
                        BiggerListHead = new ListNode(node.val);
                        BiggerListTail = BiggerListHead;
                    }else { 
                        BiggerListTail.next = new ListNode(node.val);
                        BiggerListTail = BiggerListTail.next;
                    }
                }
                
                node = node.next;
            }
    
            ListNode res;
            if(smallerListHead != null){ 
                smallerListTail.next = BiggerListHead;
                res = smallerListHead;
            }else if(BiggerListHead != null){ 
                res = BiggerListHead;
            }else{ 
                res = null;
            }
            return res;
        }
    }

#### [328. 奇偶链表][328.] ####

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

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

**示例 1:**

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

**示例 2:**

输入: 2->1->3->5->6->4->7->NULL 
    输出: 2->3->6->7->1->5->4->NULL

**题解**

class Solution { 
        public ListNode oddEvenList(ListNode head) { 
            if(head == null){ 
                return head;
            }
    
            int sum = 1;
            ListNode tail = head;
            while(tail.next != null){ 
                tail = tail.next;
                sum ++;
            }
    
            int idx = 1;
            ListNode node = head;
            ListNode pre = null;
    
            while(idx <= sum){ 
                if(idx % 2 == 0){ 
                    tail.next = node;
                    tail = node;
    
                    pre.next = node = node.next;
                }else { 
                    pre = node;
                    node = node.next;
                }
    
                idx ++;
            }
    
            tail.next = null;
            return head;
        }
    }

#### [2. 两数相加][2.] ####

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

给你两个 **非空** 的链表，表示两个非负的整数。它们每位数字都是按照 **逆序** 的方式存储的，并且每个节点只能存储 **一位** 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

**示例 1：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70][]

输入：l1 = [2,4,3], l2 = [5,6,4]
    输出：[7,0,8]
    解释：342 + 465 = 807.

**示例 2：**

输入：l1 = [0], l2 = [0]
    输出：[0]

**示例 3：**

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

**题解**

class Solution { 
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            ListNode l1Node = l1;
            ListNode l2Node = l2;
            ListNode resHead = null;
            ListNode resTail = null;
    
            boolean flag = false;
            while(l1Node != null && l2Node != null){ 
                int data = l1Node.val + l2Node.val + (flag ? 1: 0);
                //=============完全相同的部分，但实在不好抽离================
                flag = false;
                if(data >= 10){ 
                    data -= 10;
                    flag = true;
                }
                
                if(resHead == null){ 
                    resHead = resTail = new ListNode(data);
                }else { 
                    resTail.next = new ListNode(data);
                    resTail = resTail.next;
                }
                //===========================================================
    
                l1Node = l1Node.next;
                l2Node = l2Node.next;
            }
    
            ListNode other = l1Node != null ? l1Node : l2Node;
            while(other != null){ 
                int data = other.val + (flag ? 1 : 0);
                //=============完全相同的部分，但实在不好抽离================
                flag = false;
                if(data >= 10){ 
                    data -= 10;
                    flag = true;
                }
    
                if(resHead == null){ 
                    resHead = resTail = new ListNode(data);
                }else { 
                    resTail.next = new ListNode(data);
                    resTail = resTail.next;
                }
                //===========================================================
                other = other.next;
            }
    
            if(flag){ 
                resTail.next = new ListNode(1);
            }
    
            return resHead;
        }
    }

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

**示例 1:**

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

**示例 2:**

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

**题解**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
    class Solution { 
        public ListNode deleteDuplicates(ListNode head) { 
            if(head == null){ 
                return head;
            }
            
            ListNode pre = head;
            ListNode cur = head.next;
            while(cur != null){ 
                if(pre.val == cur.val){ 
                    pre.next = cur.next;
                    cur = cur.next;
                }else { 
                    pre = cur;
                    cur = cur.next;
                }
            }
    
            return head;
        }
    }

#### [237. 删除链表中的节点][237.] ####

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

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 **要被删除的节点** 。

现有一个链表 – head = \[4,5,1,9\]，它可以表示为:

![在这里插入图片描述][20210210224813544.png]

**示例 1：**

输入：head = [4,5,1,9], node = 5
    输出：[4,1,9]
    解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

**示例 2：**

输入：head = [4,5,1,9], node = 1
    输出：[4,5,9]
    解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

**提示：**

*  链表至少包含两个节点。
 *  链表中所有节点的值都是唯一的。
 *  给定的节点为非末尾节点并且一定是链表中的一个有效节点。
 *  不要从你的函数中返回任何结果。

**题解**

class Solution { 
        public void deleteNode(ListNode node) { 
            ListNode preI = node;
            ListNode i = node.next;
            while(i != null){ 
                preI.val = i.val;
                if(i.next == null){ 
                    break;
                }else{ 
                    preI = i;
                    i = i.next;
                }
            }
    
            preI.next = null;
        }
    }

[206.]: https://leetcode-cn.com/problems/reverse-linked-list/
[92. _ II]: https://leetcode-cn.com/problems/reverse-linked-list-ii/
[86.]: https://leetcode-cn.com/problems/partition-list/
[328.]: https://leetcode-cn.com/problems/odd-even-linked-list/
[2.]: https://leetcode-cn.com/problems/add-two-numbers/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/f33508938f6b4b1b8ab2f1eecf487feb.png
[83.]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
[237.]: https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
[20210210224813544.png]: /images/20221024/9253994d82f7454b9f72168034e729d2.png