链表OJ练习_if(head.val == head.next.val) head = head.next;

链表OJ练习

一、链表的删除

【题目】给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
【分析】

1. 需要判断删除节点是否为空

            if(head == null){
                return null;
            }
1
2
3

2. 删除头节点

            if(head.val == val){
                head = head.next;
            }
1
2
3

3. 删除中间节点

            ListNode prev = head; //待删除节点的前一个节点
            ListNode cur = head.next; //待删除节点
            while(cur != null) {
                if(cur.val == val) {
                    //找到了待删除节点
                    prev.next = cur.next;
                    cur = prev.next;
                }
                else {
                    //当前值不是需要删除的值,则只需更新 prev 和 cur
                    prev = prev.next;
                    cur = cur.next;
                }
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 注意：此方法忽略了第二个元素也是目标元素的情况，故应该循环判断头结点是否是要删除的节点，为了解决这个问题，最简单的方法是调整删除头结点和删除中间节点的顺序

class ListNode {
    int val = 0;
    ListNode next = null;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Solution {
        public ListNode removeElements(ListNode head, int val) {
            //在线oj提供的链表默认不带傀儡节点
            //删除时需要考虑待删除节点是否是头结点的情况
            //删除其他节点是需要找到该节点的前一个节点

            //删除头结点为空的节点
            if(head == null){
                return null;
            }

            //删除一般节点
            ListNode prev = head; //待删除节点的前一个节点
            ListNode cur = head.next; //待删除节点
            while(cur != null) {
                if(cur.val == val) {
                    //找到了待删除节点
                    prev.next = cur.next;
                    cur = prev.next;
                }
                else {
                    //当前值不是需要删除的值,则只需更新 prev 和 cur
                    prev = prev.next;
                    cur = cur.next;
                }
            }
            //先删除中间节点，再删除头结点
            if(head.val == val){
                head = head.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
23
24
25
26
27
28
29
30
31
32
33
34
35

二、反转单链表

【题目】给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
【分析】逆置的过程中需要先设定三个引用，使用prevNode记录前一个节点，curNode记录当前节点，nextNode记录下一个节点。核心操作是curNode.next = prevNode；核心代码为将当前位置的节点指向改变，使其指向前一个节点。

• step0：
• step1：
  
• step2：
  
  

    public ListNode reverseList(ListNode head) {
        //写代码的时候都要考虑到特殊情况
        if (head == null){
            return null;
        }
        //链表中只有一个节点
        if (head.next == null){
            return head;
        }
        //处理一般情况
        ListNode newHead = null;
        ListNode prevNode = null;
        ListNode curNode = head;
        ListNode nextNode = curNode.next;
        while (curNode != null){

            if (nextNode == null){
                //curNode 指向了链表的最后一个节点
                //此节点则为逆置链表的头结点
                newHead = curNode;
            }

            //为了保证 nextNode 不会失效，需要初始化 nextNode 的值
            nextNode = curNode.next;
            //更新指向
            curNode.next = prevNode;
            //更新其他引用的位置
            prevNode = curNode;
            curNode = nextNode;
        }
        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

三、返回中间节点

【题目】给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
【分析】oj题目一般默认不带傀儡节点。若要返回中间节点，则需要先求出总长度，然后对总长度除以二，设置引用从头开始遍历，遍历的步数为总长度的一半时，即可得出我们需要的结果。

class ListNode{
    int val;
    ListNode next;
    public ListNode(int v){
        val = v;
    }
}

public class LinkedList {
    //求链表长度
    public int getLength(ListNode head){
        //遍历链表即可
        int length = 0;
        for (ListNode cur = head;cur != null;cur = cur.next){
            length++;
        }
        return length;
    }
    public ListNode middleNode(ListNode head) {
        //虽然题目给出的链表是非空单链表，但是在实际开发过程中，需要加上非空判断
        if (head == null){
            return null;
        }
        //求链表的长度
        int length = getLength(head);
        //求引用走的步数
        int steps = length / 2;
        ListNode cur = head;
        for (int i = 0;i < steps;i ++){
            cur = cur.next;
        }
        return cur;
    }
}
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

四、求倒数指定节点

【题目】输入一个链表，输出该链表中倒数第k个结点
【分析】k的最大值就是单链表的长度length；又考虑到单链表只能从前往后遍历，不能从后往前遍历，故要想得到倒数第k个节点，则需要从头（head）开始走length-k步。

class ListNode{
    int val;
    ListNode next;
    public ListNode(int v){
        val = v;
    }
}

//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，
//则返回第二个中间结点
public class LinkedList {
    //求链表长度
    public int getLength(ListNode head){
        //遍历链表即可
        int length = 0;
        for (ListNode cur = head;cur != null;cur = cur.next){
            length++;
        }
        return length;
    }

    //输入一个链表，输出该链表中倒数第k个结点
    public ListNode  FindKthToTail(ListNode head,int k) {
        //判断头结点是否为空
        if (head == null){
            return null;
        }
        if (k <= 0){
            return null;
        }
        int length = getLength(head);
        if (k > length){
            return null;
        }
        //若要的到倒数第 k 个节点，就需要让引用从头开始遍历走 k 步。
        int steps = length -k;
        ListNode cur = head;
        for (int i = 0;i < steps;i++){
            cur = cur.next;
        }
        //cur指向了倒数第 k 个节点
        return cur;
    }
}
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

五、链表有序合并

【题目】将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
【分析】先设置两个引用分别指向两个链表的头结点。依次循环比较其大小，使值大者插入结果链表的末尾并更新引用指向下一个节点。任何一个引用到达链表末尾，就算循环结束。

• 不带傀儡节点的时候需要对头结点是否为空做分类讨论

    //链表的有序合并（不带傀儡节点）
    public ListNode mergeTwoLists(ListNode list1, ListNode list2)
    {
        if (list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        //两个链表都非空，则进行合并
        ListNode cur1 = list1;
        ListNode cur2 = list2;

        //创建的新链表保存合并结果
        ListNode newHead = null;

        //后续要频繁进行尾插，为了尾插方便，用改变量将尾部节点标记
        //虽然链表一般都用头结点来表示，但是也可以用引用记录其他节点。
        ListNode newTail = null;

        //循环遍历两个链表，并比较。任意引用到达链表末尾，都算循环结束
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                //把 cur1 插入到新链表末尾
                if (newTail == null){
                    //针对空链表插入
                    newHead = cur1;
                    newTail = newHead;
                }else {
                    //针对非空链表的插入
                    newTail.next = cur1;
                    newTail = newTail.next;
                }
            }else{
                //把 cur2 插入到新链表末尾
                if(newTail == null){
                    //针对空链表的插入
                    newHead = cur2;
                    newTail = newHead;
                }else {
                    //针对非空链表的插入
                    newTail.next = cur2;
                    newTail = newTail.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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

• 带傀儡节点

    //链表的有序合并（带傀儡节点）
    public ListNode mergeTwoLists(ListNode list1, ListNode list2)
    {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        //两个链表都非空，则进行合并
        ListNode cur1 = list1;
        ListNode cur2 = list2;

        //创建的新链表保存合并结果
        ListNode newHead = new ListNode(0); //傀儡节点

        //后续要频繁进行尾插，为了尾插方便，用改变量将尾部节点标记
        //虽然链表一般都用头结点来表示，但是也可以用引用记录其他节点。
        ListNode newTail = newHead;

        //循环遍历两个链表，并比较。任意引用到达链表末尾，都算循环结束
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                //把 cur1 插入到新链表末尾
                newTail.next = cur1;
                cur1 = cur1.next;  //更新循环变量
            } else {
                //把 cur2 插入到新链表末尾,针对非空链表的插入
                newTail.next = cur2;
                cur2 = cur2.next;  //更新循环变量
                }
            newTail = newTail.next;
        }
        //当上述循环结束时，意味着一定有一个引用已经先到达链表末尾，
        // 此时只需要把另外一个链表的尾部节点返回即可
        if(cur1 == null){
            newTail.next = cur2;
        }else {
            newTail.next = cur1;
        }
        //newHead是带傀儡节点的链表，返回的链表是不带傀儡节点
        return newHead.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
31
32
33
34
35
36
37
38
39
40
41
42
43
44

六、按照给定节点分类

【题目】现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
【分析】首先，遍历链表。然后将链表中标的元素和节点处的值做大小 比较，将得到的较小的值放到一个新的链表的中，将得到的较大值放到另外一个新的链表中吗，最后将两个新的链表拼接在一块即可。

public ListNode partition(ListNode pHead, int x) {
        //判断链表头结点是否为空
        if (pHead == null){
            return null;
        }
        //链表只有一个节点
        if(pHead.next == null){
            return pHead;
        }
        //处理一般情况，创建两个新链表，存储两部分结果
        //为了方便尾插，此处使用带傀儡节点的链表
        ListNode smallHead = new ListNode(0);
        ListNode smallTail = smallHead;

        ListNode largeHead = new ListNode(0);
        ListNode largeTail = largeHead;
        for (ListNode cur = pHead;cur != null;cur = cur.next){
            if(cur.val < x){
                //插入到 smallHead 末尾
//                smallHead.next = cur;
                //采用此方法的尾插是在原来的链表基础上进行操作的，
                //因此为了不破坏原理的链表，设置一个新的链表对其进行尾插操作
                smallHead.next = new ListNode(cur.val);
                smallHead = smallTail.next;
            }else {
                //插入到 largeHead 末尾
                largeHead.next = new ListNode(cur.val);
                largeHead = largeTail.next;
            }
        }
        //代码运行到此处，原链表被拆分成两个链表。
        //第一部分是小于x的元素
        //第二部分是大于x的元素
        //最后一步只需要将两部分连接成一块（首（大的）尾（小的）相接）即可
        smallTail.next = largeHead.next;
        return smallHead;
    }
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