LeetCode刷题（11）

链表相关问题

206. Reverse Linked List (Easy)

问题描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路
非递归版：使用next指针保存head的下一个位置，pre保存为pre的上一个位置（初始化为空）,head向后移动，每次移动时令head.next指向pre，之后使用pre保存当前位置，head移动到next的位置重复上述操作，直到head移动到为NULL的位置，此时pre变为了翻转链表的头指针。

递归版：
递归出口：if (head=null || head.next=null )return head;
将head和head.next看做两个部分，对head.next后面的链表进行反转，新链表的头指针为pre
然后让新链表的尾结点即head.next.next指向旧头结点：head.next.next=head
最后让head的后继节点指向空

代码（非递归版）

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null,next = null;
        while (head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

代码（递归版）

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode nextHead = head.next;
        ListNode pre = reverseList(head.next);
        nextHead.next = head;
        head.next = null;
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

21. Merge Two Sorted Lists (Easy)

问题描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路
非递归：创建一个新的链表头结点head，之后分别使用p,p1,p2指针指向head，listNode1,listNode2，然后将listNode1和listNode2中指向小的节点放在p的后继节点上，同时p向后移动，p1和p2中指向元素值小的那一个指针也同时向后移。当其中一个链表遍历完时，直接使用p.next指向未遍历完的链表当前遍历指针上，最后返回head.next作为新链表的头指针。

递归版：
递归出口：
if (list1 == null) { return list2; }
if (list2 == null) {return list1; }

将每个链表看做两个部分，首元素和head.next链表；
if(list1.val < list2.val)，list1作为新链表的头结点，合并list1.next链表和list2链表；
if(list1.val >= list2.val)，list2作为新链表的头结点，合并list2.next链表和list1链表；

代码（非递归）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p = list1,q = list2;
        ListNode newList = new ListNode(-1);
        ListNode newP = newList;
        while (p!=null && q!=null){
            if(p.val>q.val){
                newP.next = q;
                q = q.next;
                newP = newP.next;
            }else {
                newP.next = p;
                p = p.next;
                newP = newP.next;
            }
        }
        if(p!=null){
            newP.next = p;
        }
        if(q!=null){
            newP.next = q;
        }
        return newList.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

代码（递归）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

24. Swap Nodes in Pairs (Medium)

问题描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入输出样例

示例 1：

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

示例 2：

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

思路
可以考虑先对前两个元素进行交换，确定好头结点的位置后，再对后面的元素经过两两交换。
交换的思路是：

当p移动到末尾位置或者为null时不再移动

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next==null) return head;
        ListNode p = head;
        ListNode next = head.next;
        ListNode pre = null;
        p.next = next.next;
        next.next = p;
        pre = p;
        p = p.next;
        head = next;
        while (p != null && p.next!=null){
            next = p.next;
            p.next = next.next;
            next.next = p;
            pre.next = next;
            pre = p;
            p = p.next;
        }
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

160. Intersection of Two Linked Lists (Easy)

问题描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

思路
两个遍历指针分别指向两个链表开头，如果一个链表走到头则重新指向另外一个指针开头，这样当两个指针再次相遇时就是相交的位置。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while (p!=q){
            p = p==null?headB:p.next;
            q = q==null?headA:q.next;
        }
        return p;
    }
}
1
2
3
4
5
6
7
8
9
10
11

234. Palindrome Linked List (Easy)

问题描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路
先使用快慢指针找到链表中点，再把链表切成两半；然后把后半段翻转；最后比较两半是否相等。

代码

/**
 * 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 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 = reverse(slow);
        fast = head;
        while (slow!=null && fast!=null){
            if(slow.val != fast.val)return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
        
    }
    
    private ListNode reverse(ListNode head){
        if(head == null || head.next==null) return head;
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
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

83. Remove Duplicates from Sorted List (Easy)

问题描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

输入输出样例
示例 1：

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

示例 2：

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

问题描述
使用一个next指针每次直到当前指针的下一个位置，如果下一个位置的值等于当前位置的值，则删除next值向的元素（可能有多个连在一起，需要循环删除）

代码

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null || head.next==null)return head;
        ListNode p = head;
        ListNode next = null;
        while (p!=null){
            next = p.next;
            while (next!=null && next.val == p.val){
                p.next = next.next;
                next = p.next;
            }
            p = p.next;
        }
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

328. Odd Even Linked List (Medium)

问题描述
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

输入输出样例
示例 1:

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

示例 2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

思路
用两个指针p1,p2分别指向偶链表和奇链表的头结点，然后分别用p1.next.next和p2.next.next节点作为p1,p2的后继节点。然后p1,p2向后遍历，当p1，p2其中一个到达尾结点位置时停止遍历，之后直接将偶链表头指针作为p1的后继节点即可。

代码

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null || head.next.next==null) return head;
        ListNode tailHead = head.next; 
        ListNode q = head;//偶数节点头指针
        ListNode p = tailHead; //技术节点头指针

        ListNode q1 = null;
        ListNode p1 = null;
        while (q.next!=null&&p.next!=null){
            q1 = q.next.next;
            p1 = p.next.next;
            q.next = q1;
            p.next = p1;
            q = q1;
            p = p1;
        }
        q.next = tailHead;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

19. Remove Nth Node From End of List (Medium)

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

思路
使用一个快指针比慢指针多k+1步，这样当快指针走到结尾时，只需要删除慢指针前面的数即可。

考虑一个特殊位置：如果第n个节点刚好是开头时，返回head.next即可。

代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = head;
        if(p==null) return null;
        for(int i=0;i<=n;i++){//快指针先向前走k+1步
            if(p==null) return head.next;//如果走到了空的位置，说明删除的是第一个节点
            p = p.next;
        }
        ListNode pre = head;
        while (p!=null){
            pre = pre.next;
            p = p.next;
        }
        pre.next = pre.next.next;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

148. Sort List (Medium)

问题描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

思路
可以使用链表版的归并排序。即将链表从中间分成两个部分，分别对每个部分进行归并排序，之后将两个有序的链表合并在一起。从中间分开可以使用快慢指针，快指针指向结尾的时候，慢指针就指向了中间的位置。需要注意的点是，需要将两个链表从中间断开。

代码

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){//快指针指向结尾或者为空时都结束
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;//fast重新指向了右边链表的头结点
        slow.next = null;//注意要断开两边的链表，否则下次递归时快慢指针会出问题
        ListNode listLeft = sortList(head);
        ListNode listRight = sortList(fast);
        return merge(listLeft,listRight);
    }
    
    //合并两个有序的链表
    public ListNode merge(ListNode list1,ListNode list2){
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val<list2.val){
            list1.next = merge(list1.next,list2);
            return list1;
        }else {
            list2.next = merge(list1,list2.next);
            return list2;
        }
    }
}
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