数据结构之链表练习题(leetCode）_先将键盘输入的一组整数依次存入循环链表(尾插法),然后删除头部第一个元素,最后将

1.移除链表元素（203）

题目: 给你一个链表的头节点 head 和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
方法一：这道题是删除链表中所有等于val的元素，需要考虑两种情况。

1. 头节点是要删除的节点，这时候我们循环判断head的值，但是head不能为空，这样就是链表中没元素了。
2. 头节点确定不是要删除的结点，我们就遍历链表判断后面的值，因为我们找的是前驱结点，所以我们要保证待删除的结点不能为空，否则会造成空指针异常。造成了pre遍历到最后一个结点，已经没有要判断的结点了。

public ListNode removeElements(ListNode head, int val) {
    while(head != null && head.val == val){
        head = head.next;
    }
    for (ListNode pre = head; pre != null; pre = pre.next) {
        while(pre.next != null && pre.next.val == val) {
            pre.next = pre.next.next;
        }
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11

方法二：递归
三步骤：首先，判断是否能拆分：这道题可以拆成head.val == val和剩下结点是否有val
其次：拆封后解决思路相同
最后：存在终止条件

1. 理解函数的语义：传入头结点和待删除的值，函数就能删除所有等于val的元素
2. 将链表分为头结点和其他结点，因为我们只能知道头结点。
3. 把除头结点之后的链表的删除工作交给子函数运行，子函数就能把元素删除
4. 判断头结点是否为需要删除的结点，若是，返回头结点的下一个结点；反之，返回头结点

public ListNode removeElements(ListNode head, int val) {
	//链表内没有元素，终止条件
    if (head == null){
        return null;
    }
    head.next = removeElements(head.next,val);
    //删除操作
    if (head.val == val){
        return head.next;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.删除排序链表中的重复元素（83）

题目：给定一个已排序的链表的头head， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表。
输入：head = [1,1,2]
输出：[1,2]
方法一：

1. 这道题我们不知道要删除的元素是谁，所以我们需要引入两个指针去比较。
2. 当pre.val == cur.val,说明pre是第一个重复的元素，所以我们保留这个元素，而cur是要删除的元素，所以pre.next = cur.next，然后让cur向后走，等于走一步删一步。
3. 当pre.val!=cur.val,说明他们不是要删除的元素，一起向后走。直到cur==null，循环完毕，返回头结点。

public ListNode deleteDuplicates(ListNode head) {
    //当链表为空或者只有一个元素的时候，不可能有重复的元素
    if (head == null || head.next == null){
        return head;
    }
    ListNode pre = head;
    ListNode cur = pre.next;
    while(cur != null){
        if (pre.val != cur.val) {
            pre = pre.next;
            cur = cur.next;
        } else {
            pre.next = cur.next;
            cur = cur.next;
        }
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：递归

1. 将题目拆封成头结点和之后的结点两部分。
2. 理解函数语义：一个有序的链表，传入头结点，可以将重复元素删除，只保留一个重复的元素，返回删除后的头结点
3. 第二个结点之后的删除交给子函数去运行。
4. 由于我们只知道头结点，所以我们将当前的头结点和返回后的头结点相比较，如果相等，就把当前头结点删了，返回head.next；反之，返回head。

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    head.next = deleteDuplicates(head.next);
    if (head.val == head.next.val) {
        return head.next;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10

3.删除排序链表中的重复元素 II（82）

题目：给定一个已排序的链表的头head,删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表 。
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
方法一：

1. 这里引入了三个指针.如果两个指针的话，当pre指向重复元素的话，就删不掉了。因为重复元素都要删除，所以pre要指向不重复的元素，我们就让剩下两个指针判断结点是否重复。
2. 当cur.val != next.val,三指针同时向后移动
3. 当cur.val == next.val,循环让next向后移动，移动到第一个和cur不相等的元素，意味着pre之后next之前的元素都是要删除的元素。所以pre.next = next把元素删除
4. 删除后cur和next向后移动一个结点。pre不能向后移动，因为有可能cur和next依旧相等。

public ListNode deleteDuplicates(ListNode head) {
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode pre = dummyHead;
    ListNode cur = pre.next;
    while(cur != null) {
        ListNode next= cur.next;
        if (next == null){
            //链表内只有一个节点或者链表遍历完了
            break;
        } else {
            //链表内至少有两个结点
            //不相等，三指针同时向后移动，在下一次循环开始的时候，next会向后走一步
            if (cur.val != next.val) {
                pre = pre.next;
                cur = cur.next;
            } else {
            	//相等时，让next向后走到第一个不相等的元素
                while(next != null && cur.val == next.val) {
                    next = next.next;
                }
                pre.next = next;
                //cur向后走一步
                cur = next;
            }
        }
    }
    //返回头结点
    return dummyHead.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
28
29
30

图解：

方法二：递归

1. 理解语义：传入头结点，这个函数能把所有重复元素都删除，并返回新的头结点。所以我们只要处理头结点就可以了
2. 如果head.val != head.next.val,证明第一个结点和第二个结点不相等，我们把第二个结点开始交给子函数处理就可以了。
3. 循环判断head.val是否等于head.next.val，相等的话把头删掉，一直向后走，走第一个与头不相等的结点。循环判断结束后，nextHead一定是不重复的头结点，我们把这个结点作为新的头结点传入交给子函数处理。

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null){
        return head;
    }
    if (head.val != head.next.val) {
        head.next = deleteDuplicates(head.next);
        return head;
    } else {
    	//删头结点
        ListNode nextHead = head.next;
        while (nextHead != null && head.val == nextHead.val){
            nextHead = nextHead.next;
        }
        return deleteDuplicates(nextHead);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.反转链表(206)

题目：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
方法一：这道题的核心思想就是头插法，在遍历链表的同时，新建节点进行头插到新链表，当遍历完了，就反转了整个链表。

public ListNode reverseList(ListNode head) {
    ListNode dummyHead = new ListNode();
    while(head != null) {
        ListNode node = new ListNode(head.val);
        node.next = dummyHead.next;
        dummyHead.next = node;
        head = head.next;
    }
    return dummyHead.next;
}
1
2
3
4
5
6
7
8
9
10

方法二：迭代
核心思想：定义三个指针，pre，cur,next。原先的1->2,现在需要2->1,1->null
让pre = null,cur = head,next暂存下一个需要处理的结点，因为没有next我们就找不到下一个节点了，和谈反转呢？
当cur走向null，这时候pre正好是反转后的头结点，返回pre就可以了

public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) {
        return head;
    }
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法三：递归

1. 理解语义：传入头结点，我们能将链表反转，并返回新的头结点
2. 第二个节点开始交给子函数去反转，这道题返回后的头结点newHead是5.然后只要把原先的头结点链接到最后，并让原先头结点指向空就可以了。
3. 因为要让原先的头结点连到最后，需要暂存一下原链表的第二个结点，也就是反转后的倒数第二个节点。

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null){
        return head;
    }
    ListNode node = head.next;
    ListNode newHead = reverseList(head.next);
    node.next = head;
    //不能省略，会成环
    head.next = null;
    return newHead;
}
1
2
3
4
5
6
7
8
9
10
11

图示:

5.链表的中间结点（876）

题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
方法一：1. 计算链表中结点个数
2. 遍历链表找到中间节点
3. 返回中间节点

public ListNode middleNode(ListNode head) {
    int count = 0;
    for(ListNode x = head; x != null; x = x.next) {
        count ++;
    }
    ListNode x = head;
    for (int i = 0; i < count / 2; i++) {
        x = x.next;
    }
    return x;
}
1
2
3
4
5
6
7
8
9
10
11

方法二：快慢指针(双引用)

1. 引入两个指针，一个走一步，一个走两步，当快的指针指向空或者快的指针的下一个结点指向空。慢的指针正好走到了中间结点。
2. 核心，两个指针，让一个引用先走或者多走几步

public ListNode middleNode(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9

推导：

设路程为s，slow的速度为V₁,fast的速度为V₂，所用时间为t
当V₂ = 2V₁
S = V₂ * t
S/2 = V₁ * t //正好是中间的结点

6.链表中倒数第k个节点（剑指 Offer 22）

题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
方法一：遍历链表

public ListNode getKthFromEnd(ListNode head, int k) {
    int count = 0;
    for (ListNode x = head; x != null; x = x.next) {
        count ++;
    }
    ListNode node = head;
    for (int i = 0; i < count - k; i++) {
        node = node.next;
    }
    return node;
}
1
2
3
4
5
6
7
8
9
10
11

方法二

1. 定义两个指针fast和slow,让fast先后k步，然后fast和slow一起向后走，当fast走到空，slow正好在倒数第k个位置
2. 因为fast和slow的相对距离为k步，当fast走到终点，他们的相对距离还是k步，正好就是倒数第k个位置

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast = head;
    for (int i = 0; i < k ; i++) {
        fast = fast.next;
    }
    ListNode slow = head;
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12

7.回文链表

题目：给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是返回 true ；否则返回 false。
输入：head = [1,2,2,1]
输出：true
方法一：新建一个链表，反转原链表到新链表上。同时遍历原链表和新链表，当他们有一个值不相等时，就不是回文数

public ListNode reverseList(ListNode head) {
    ListNode dummyHead = new ListNode();
    while(head != null) {
        ListNode node = new ListNode(head.val);
        node.next = dummyHead.next;
        dummyHead.next = node;
        head = head.next;
    }
    return dummyHead.next;
}
public boolean isPalindrome(ListNode head) {
    ListNode newLink = reverseList(head);
    while(head != null) {
        if (head.val != newLink.val) {
            return false;
        }
        head = head.next;
        newLink = newLink.next;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二
从中间节点之后的链表反转，与中间节点之前的链表进行对比，如果不一样，返回false，反之，ture。

public ListNode reverse(ListNode head){
    if (head == null || head.next == null){
        return head;
    }
    ListNode node = head.next;
    ListNode newHead = reverse(head.next);
    node.next = head;
    head.next = null;
    return newHead;
}
//找中间结点
public ListNode middleNode(ListNode head){
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
public boolean isPalindrome(ListNode head) {
    ListNode midNode = middleNode(head);
    ListNode resHead = reverse(midNode);
    while(resHead != null){
        if (head.val != resHead.val){
            return false;
        }
        resHead = resHead.next;
        head = head.next;
    }
    return true;
}
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

8.合并两个有序链表（21）

题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
方法一：拼接链表
核心：尾插

1. 当list1为空,直接返回list2;当list2为空，直接返回list1.
2. 当两个链表都不为空，比较两个链表中结点的大小。
3. 两个链表遍历，取出最小值，拼接到链表的尾部
4. 拼接完了后，当list1还有剩下的结点，将list1的结点拼接到新链表尾部
5. 拼接完了后，当list2有剩下的结点，将list2结点拼接到新链表尾部

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null){
        return list2;
    }
    if (list2 == null){
        return list1;
    }
    ListNode dummyHead = new ListNode();
    //新链表的尾结点
    ListNode tail = dummyHead;
    while(list1 != null && list2 != null) {
        if(list1.val <= list2.val) {
            tail.next = list1;
            tail = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            tail = list2;
            list2 = list2.next;
        }
    }
    if (list1 == null){
        tail.next = list2;
    }
    if (list2 == null){
        tail.next = list1;
    }
    return dummyHead.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
28
29

方法二:递归
边界条件一样

1. 理解语义：传入两个升序的链表，就能拼接成一个大的升序链表，并返回拼接后的头结点。
2. 这里我们只知道两个链表的头结点，所以我们只要比较这两个头结点的大小。
3. 如果head1 <= head2,说明head1一定是拼接后链表的头结点，因为是最小的一个。从list1第二个节点开始和整个list2交给子函数处理，他能返回拼接后的头结点。
4. 我们找出的最小结点的下一个节点就是子函数处理完之后的头结点，所以两个一拼接，就完成了这道题。

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(list2.next,list1);
        return list2;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

9.分割链表（02.04）

题目:给你一个链表的头节点head和一个特定值x，请你对链表进行分隔，使得所有小于x的节点都出现在大于或等于x的节点之前。
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
分析：

1. 这道题我们可以采用分割 + 拼接的方法
2. 首先，创建两个链表，一个链表存放小于x的值；一个链表存放大于x的值。最后将大链表拼接到小链表之后就可以了。
3. 注意，拆封完了之后大链表还会挂在结点，我们将这个大链表的尾结点的下一个结点的指向空就可以了。

public ListNode partition(ListNode head, int x) {
    if (head == null || head.next == null){
        return head;
    }
    ListNode smallHead = new ListNode();
    ListNode smallTail = smallHead;
    ListNode bigHead = new ListNode();
    ListNode bigTail = bigHead;
    while (head != null) {
        if (head.val < x) {
            smallTail.next = head;
            smallTail = head;
        } else {
            bigTail.next = head;
            bigTail = head;
        }
        head = head.next;
    }
    bigTail.next = null;
    smallTail.next = bigHead.next;
    return smallHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

10.相交链表（160）

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

分析

1. 当两个链表有相交结点的时候,让两个引用l1,l2分别从前向后走,当l1走到空时，让l1从headB开始走；当l2走到空时，让l2从headA开始走。这样之后，便会找到相交的结点。
2. 当两个结点不相交的时候，l1走完走headB链表；l2走完走headA链表，当两个链表都走向空的时候，意味着两个链表没有相交结点
3. 智力题，我人看傻了

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA;
    ListNode l2 = headB;
    while (l1 != l2) {
        l1 = l1 == null ? headB : l1.next;
        l2 = l2 == null ? headA : l2.next;
    }
    return l1;
}
1
2
3
4
5
6
7
8
9

图解:

11.环形链表(141)

题目：给你一个链表的头节点head，判断链表中是否有环。

解析

1. 这道题我们可以比喻为环形操场跑步，两个人在跑步，若一个人的速度比另一个快，不管跑了多少圈，一定会“套圈”，追上慢的那个人。
   快慢指针，快的走两步，慢的走一步，当快的追上了慢的，就意味着是个环形链表；当快指针走向空，代表链表没环。

public boolean hasCycle(ListNode head) {
    ListNode fast = head,slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        //追上了
        if (fast == slow){
            return true;
        }
    }
    //直线
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

12.反转链表 II(92)

题目:给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

方法一：三指针 + 头插

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    //pre指向待反转区间的前驱节点
    ListNode pre = dummyHead;
    //cur指向待反转区间的第一个节点
    ListNode cur = pre.next;
   	//让pre和cur走left - 1步，走到对应位置
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
        cur = cur.next;
    }
    //只需要反转right - left次就可以
    for (int i = 0; i < right - left; i++) {
        //暂存下一个要处理的结点
        ListNode next = cur.next;
        //先删除next，在头插到pre的后面
        cur.next = next.next;
        //头插
        next.next = pre.next;
        pre.next = next;
    }
    return dummyHead.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