链表算法题

反转链表

//使用栈解决
import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
    Stack<ListNode> stack= new Stack<>();
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    //栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点，一定要让他的next
    //等于空，否则会构成环
    node.next = null;
    return dummy;
}
}
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

//方法二;头插法迭代
public ListNode ReverseList(ListNode head) {
    //新链表
    ListNode newHead = null;
    while (head != null) {
        //先保存访问的节点的下一个节点，保存起来
        //留着下一步访问的
        ListNode temp = head.next;
        //每次访问的原链表节点都会成为新链表的头结点，
        //其实就是把新链表挂到访问的原链表节点的
        //后面就行了
        head.next = newHead;
        //更新新链表
        newHead = head;
        //重新赋值，继续访问
        head = temp;
    }
    //返回新链表
    return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

BM2 链表内指定区间反转

m到n反转可类似反转链表头插法迭代方法
step 1：我们可以在链表前加一个表头，后续返回时去掉就好了，因为如果要从链表头的位置开始反转，在多了一个表头的情况下就能保证第一个节点永远不会反转，不会到后面去。
step 2：使用两个指针，一个指向当前节点，一个指向前序节点。
step 3：依次遍历链表，到第m个的位置。
step 4：对于从m到n这些个位置的节点，依次断掉指向后续的指针，反转指针方向。
step 5：返回时去掉我们添加的表头。

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //加个表头
        ListNode res = new ListNode(-1); 
        res.next = head;
        //前序节点
        ListNode pre = res; 
        //当前节点
        ListNode cur = head; 
        //找到m
        for(int i = 1; i < m; i++){ 
            pre = cur;
            cur = cur.next;
        }
        //从m反转到n
        for(int i = m; i < n; i++){ 
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        //返回去掉表头
        return res.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

BM3 链表中的节点每k个一组翻转

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(k <= 1 || head == null)    return head;
        int len = length(head);
        int sx = len / k;//分成sx块向下取整（默认向下） 因为处不尽的后面必然凑不满k个
        
        ListNode res = new ListNode(-1);
        ListNode now = res;
        for(int i =0; i < sx; i++){
            ListNode tmp = null;
            for(int j = 0 ;j < k;j++){//将第i块的元素翻转
                ListNode tt = head.next; 
                head.next = tmp;
                tmp = head;
                head = tt;
            }
            now.next = tmp;
            while(now.next != null) now = now.next; //将now更新到最前的一个点
        }
        now.next = head; 
        return res.next;
        
    }
    public int length(ListNode now){  //获取链表长度
        int cnt = 0;
        if(now != null) cnt = 1;
        while(now.next != null) {cnt++;now = now.next;}
        return cnt;
    }
}
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

//递归写法
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
       ListNode tail = head;
        for(int i = k;i > 0; i--){
           if(tail != null) tail = tail.next;
            else return head;
       }
        //翻转时需要的前序和当前节点
        ListNode pre = null;
        ListNode cur = head;
        while(cur!= tail){
            //翻转
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            
        }
        //当前尾指向下一段要翻转的链表
        head.next = reverseKGroup(tail, k);
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//使用队列
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
       // write code here
        if(k <= 1 || head == null) return head;
        Stack<ListNode> st = new Stack<ListNode>();    //模拟栈
        ListNode result = new ListNode(0);
        ListNode now = result;
        int cnt = 0;
        while(true){
            for(int i = 0; i < k; i ++){    //将当前链表前k个存入栈中
                st.push(head);
                head = head.next;
                cnt ++;
                if(head == null) break;
            }
            if(cnt == k){    //如果当前栈中有k个元素则一一取出存入链表
                while(!st.isEmpty()){
                    now.next = st.pop();
                    now = now.next; now.next = null;
                }
            }
            if(head == null) break;   //如果链表取完了跳出循环
            cnt = 0;
        }
        ListNode end = null;
        while(!st.isEmpty()){    //如果栈中还有剩下的就说明是最后的一块直接取栈底即可
            end = st.pop();
        }
        now.next = end;
        return result.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

BM6 判断链表中是否有环

//快慢指针法
public class Solution {
    public boolean hasCycle(ListNode head) {
        //先判断链表为空的情况
        if(head == null) 
            return false;
        //快慢双指针
        ListNode fast = head; 
        ListNode 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
14
15
16
17
18
19
20
21
22
23
24

BM7 链表中环的入口结点

方法1：hash法，记录第一次重复的结点。时间空间复杂度都是O(N)

public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 使用set来记录出现的结点
        HashSet<ListNode> set = new HashSet<>();
        while(pHead != null){
           // 当set中包含结点，说明第一次出现重复的结点，即环的入口结点
            if(set.contains(pHead)){
                return pHead;
            }
            // set中加入未重复的结点
            set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：快慢指针。时间复杂度都是O(N)，空间复杂度O(1)

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        
        ListNode slow = pHead,fast = pHead;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                        slow = pHead;
                    while(slow != fast){
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
            }
        }
        return null;
     
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

BM8 链表中倒数最后k个结点

//方法1：先找长度，最后再找K
import java.util.*;
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int n = 0;
        ListNode p = pHead;
         //遍历链表，统计链表长度
        while(p != null){
            n++;
            p = p.next;
        }
        //长度过小，返回空链表
        if(n < k) 
            return null;
        p = pHead;
        //遍历n-k次
        for(int i = 0; i < n - k; i++) 
            p = p.next;
        return p;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//快慢指针法
import java.util.*;
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int n = 0;
        ListNode fast = pHead; 
        ListNode slow = pHead;
        //快指针先行k步
        for(int i = 0; i < k; i++){  
            if(fast != null)
                fast = fast.next;
            //达不到k步说明链表过短，没有倒数k
            else 
                return slow = null;
        }
        //快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while(fast != null){ 
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

BM9 删除链表的倒数第n个节点

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    //1,2,3,4,5
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
       ListNode Head = new ListNode(-0);
        Head.next =head;
        ListNode slow = Head,fast = Head;//开始的双指针都指向头节点
        for(int i = 0;i < n + 1;i++){
            fast = fast.next;//fast最后指向倒数第n - 1个节点
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return Head.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

BM10 两个链表的第一个公共结点

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 =  pHead1,l2 = pHead2;
        while(l1 != l2){
            l1=(l1 == null)?pHead2:l1.next;
            l2=(l2 == null)?pHead1:l2.next;
        }
        
        return l1;
        
 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

//方法1:将两个链表反转
public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);
        ListNode res = null;
        int val = 0;
        while(h1 != null || h2 != null){
            int sum = val;
            if(h1 != null) {sum += h1.val; h1 = h1.next;}
            if(h2 != null) {sum += h2.val; h2 = h2.next;}
            ListNode node = new ListNode(sum %10);
            node.next = res;
            res = node;
            val = sum/10;    
        }
        if(val > 0){
            ListNode node = new ListNode(val);
            node.next = res;
            res= node;
        }
        return res;
        
    }
    public ListNode reverse(ListNode head){
        ListNode res = null;
        ListNode cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = res;
            res = cur;
            cur = tmp;
        }
        return res;
    }
}
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

//方法2：利用辅助站
public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1 == null)
            return head2;
        if(head2 == null){
            return head1;
        }
        // 使用两个辅助栈，利用栈先进后出
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        
        // 将两个链表的结点入栈
        while(head1 != null){ stack1.push(head1);head1 = head1.next;}
        while(head2 != null){ stack2.push(head2);head2 = head2.next;}
        int val = 0;// 进位
        
        ListNode res = null; // 创建新的链表头节点
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            int sum = val;
            if(!stack1.isEmpty()) sum+=stack1.pop().val;
            if(!stack2.isEmpty()) sum+=stack2.pop().val;
             ListNode node = new ListNode(sum % 10);
            node.next = res;
            res = node;
            
            val = sum /10;
           
            
        }
        if(val > 0){
           ListNode node = new ListNode(val);
            node.next = res;
            res = node;
        }
        return res;
    }
}
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