rhb_blog

rao的博客

0%

Algorithm__链表

发表于 更新于 分类于 ，

链表

链表的注意点

  • 出现了环，导致了死循环
  • 分不清楚边界，导致边界出错
  • 搞不清递归

环

  • 判断是否有环，以及环的位置————快慢指针算法

边界

  • 当题目中的头节点需要进行操作时，可能会被移除时，要考虑使用虚拟节点，也就是头节点。这样操作就会避免对第一个节点的讨论

前后序

相较于树，在链表中只有一个后续指针，只有前序和后序，没有中序遍历。

如果是前序遍历，那么你可以想象前面的链表都处理好了，怎么处理的不用管。相应地如果是后序遍历，那么你可以想象后面的链表都处理好了，怎么处理的不用管。

  1. e.g.前序遍历
1
2
3
4
5
6
7
8
def dfs(head,pre):
    if not head return pre//递归的结束条件
    next=head.next
    ##此处添加主逻辑
    head.next = pre
    dfs(next,head)

dfs(head,None)

一些技巧

头结点————虚拟结点

头结点不需要参与运算，不需要特殊判断

快慢指针

判断链表是否有环以及环的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null)return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null&&fast.next!=null)//考虑了链表的长度可能为奇数也可能是偶数的情况
        {//快慢指针相遇即表示为存在一个环
            if(fast==slow)return true;
            fast=fast.next.next;
            slow=slow.next;
        }
        return false;
    }
}

leetcode题目

Leetcode 61.旋转链表

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
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null)return head;
        ListNode pre_newHead = new ListNode();//
        ListNode temp = new ListNode();
        pre_newHead = head;
        temp=head;
        for(int i=0;i<k;i++)
        {
            if(temp.next!=null)
                temp=temp.next;
            else
            {
                temp=head;//转回去了
            }
        }
        while(temp.next!=null)
        {
            pre_newHead = pre_newHead.next;
            temp = temp.next;
        }
        temp.next = head;//首位相连构成循环链表
        head=pre_newHead.next;
        pre_newHead.next=null;
        return head;   
    }
}

Leetcode 82.删除排序链表中的重复元素

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
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        
        if(head==null)return null;
        if(head.next==null)return head;
        ListNode dummyhead = new ListNode(0,head);//头指针
        ListNode q = new ListNode();
        ListNode pre = new ListNode();
        pre=dummyhead;
        q=head;
        while(q!=null)
        {
            if(q.next!=null&&q.val==q.next.val){
                while(q.next!=null&&q.val==q.next.val)//遇到重复的节点
                {
                    q=q.next;//遍历到重复节点的末端
                }            
                pre.next=q.next;
            }
            else
            {
                pre = q;//pre往后移动
            }
            q=q.next;
        }
        return dummyhead.next;
    }
}

此题最为巧妙的是运用了头指针，这样可以减少对第一个元素的讨论。

Leetcode .反转链表

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
//迭代
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre=null;
        while(cur!=null)
        {
            ListNode nextTemp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextTemp;
        }
        return pre;
    }
}
//递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

Leetcode 92.反转链表2

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
/**
 * 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) {
            if(head==null)return null;
            ListNode pre = new ListNode(0,head);//防止m=1的情况
            ListNode dummy =pre;
            ListNode cur = head;
            //移动到待反转的位置上
            while(m>1)
            {
                pre=cur;
                cur=cur.next;
                m--;
                n--;
            }
            ListNode change_begin_pre =pre;
            ListNode change_begin=cur;
            ListNode temp=null;
        //对链表进行反转
            while(n>0)
            {
                temp = cur.next;
                cur.next=pre;
                pre=cur;
                cur=temp;
                n--;
            }
            change_begin_pre.next=pre;
            change_begin.next=cur;
            return dummy.next;
    }
}

Leetcode 142.环形链表2

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
//还是使用左右指针
 /*概括一下：
假设慢指针走了s步，则快指针走了2s步
f=2s （快指针每次2步，路程刚好2倍）
f = s + nb (相遇时，刚好多走了n圈）
推出：s = nb
从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(true)
        {
            if(fast==null||fast.next==null)return null;
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow)break;
        }
        fast=head;
        while(fast!=slow)
        {
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

Leetcode 234.回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//常规方法是可以想到的，这道题的递归是不容易想到的
class Solution {
    private ListNode frontPointer;//正方向进行迭代

    private boolean recursivelyCheck(ListNode currentNode) 
    {
        if (currentNode != null) {
            //currentNode指针是先到尾节点，由于递归的特性再从后往前进行比较
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }
    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
}

Leetcode 143.重排链表

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
48
49
class Solution {
    public void reorderList(ListNode head) {
        if(head==null)return ;
        if(head.next==null)return ;
        ListNode slow = head;
        ListNode fast = head.next;
        while(true)
        {
            if((fast!=null&&fast.next==null)||fast==null)
            {
                break;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        //无论链表的长度是奇数还是偶数，都是从slow指针的next结点进行比较
        ListNode temp = slow.next;
        slow.next=null;//前半截的链表进行截断
        temp = reverseList(temp);
       mergeList(head,temp);
    }
    //进行反转
     private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
    //链表进行合并
     public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }
}

Leetcode 148.排序链表

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
/* 知识点1：归并排序的整体思想
 * 知识点2：找到一个链表的中间节点的方法
 * 知识点3：合并两个已排好序的链表为一个新的有序链表
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;//找到中间结点
        slow.next=null;
        ListNode left = sortList(head); //递归排序前一段链表
        ListNode right = sortList(temp); //递归排序后一段链表
        return merge(left,right);
    }
     public ListNode merge(ListNode h1,ListNode h2){ //合并两个有序链表
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(h1!=null && h2!=null){
            if(h1.val < h2.val){
                p.next = h1;
                h1 = h1.next;
            }else{
                p.next = h2;
                h2 = h2.next;
            }
            p = p.next;
        }
        if(h1!=null)    p.next = h1;
        else if(h2!=null) p.next = h2;
        return dummy.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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//迭代
class Solution {
    public ListNode sortList(ListNode head) {
        int length = getLength(head);
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
       
        for(int step = 1; step < length; step*=2){ //依次将链表分成1块，2块，4块...
       /*第一轮合并时intv = 1，即将整个链表切分为多个长度为1的单元，并按顺序两两排序合并，合并完成的已排序单元长度为2。
第二轮合并时intv = 2，即将整个链表切分为多个长度为2的单元，并按顺序两两排序合并，合并完成已排序单元长度为4。
以此类推，直到单元长度intv >= 链表长度，代表已经排序完成。
*/
            //每次变换步长，pre指针和cur指针都初始化在链表头
            ListNode pre = dummy; 
            ListNode cur = dummy.next;
            while(cur!=null){
                ListNode h1 = cur; //第一部分头 （第二次循环之后，cur为剩余部分头，不断往后把链表按照步长step分成一块一块...）
                ListNode h2 = split(h1,step);  //第二部分头
                cur = split(h2,step); //剩余部分的头
                ListNode temp = merge(h1,h2); //将一二部分排序合并
                pre.next = temp; //将前面的部分与排序好的部分连接
                while(pre.next!=null){
                    pre = pre.next; //把pre指针移动到排序好的部分的末尾
                }
            }
        }
        return dummy.next;
    }
    public int getLength(ListNode head){
    //获取链表长度
        int count = 0;
        while(head!=null){
            count++;
            head=head.next;
        }
        return count;
    }
    public ListNode split(ListNode head,int step){
        //断链操作 返回第二部分链表头
        if(head==null)  return null;
        ListNode cur = head;
        for(int i=1; i<step && cur.next!=null; i++){
            cur = cur.next;
        }
        ListNode right = cur.next;
        cur.next = null; //切断连接
        return right;
    }
    public ListNode merge(ListNode h1, ListNode h2){
    //合并两个有序链表
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while(h1!=null && h2!=null){
            if(h1.val < h2.val){
                p.next = h1;
                h1 = h1.next;
            }
            else{
                p.next = h2;
                h2 = h2.next;
            }
            p = p.next;           
        }
        if(h1!=null)    p.next = h1;
        if(h2!=null)    p.next = h2;

        return head.next;     
    }
}

作者：cherry-n1
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-di-gui-die-dai-xiang-jie-by-cherr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。