算法-链表

发表于 | 分类于 ，

链表和问题

两个非空链表表示两个数，数字倒叙排列，比如 (2 -> 4 -> 3) + (5 -> 6 -> 4) 表示 342 + 465 = 807.， 最后输出应该为7 -> 0 -> 8。

注意进位问题就好了。

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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class AddTwoNumber_2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode h1 = l1, h2 = l2;
        ListNode result = new ListNode(0);
        ListNode cur;
        int c = 0;
        cur = result;
        while (h1 != null || h2 != null || c == 1) {
            int tmp;
            if (h1 == null && h2 == null) {
                tmp = c;
            } else if (h1 == null) {
                tmp = c + h2.val;
            } else if (h2 == null) {
                tmp = c + h1.val;
            } else {
                tmp = c + h1.val + h2.val;
            }
            cur.next = new ListNode(tmp % 10);
            c = tmp / 10;
            cur = cur.next;
            if (h1 != null)
                h1 = h1.next;
            if (h2 != null)
                h2 = h2.next;
        }
        return result.next;
    }
}

和上题类似，只是数字存储为顺序存储，解决方法为引入栈和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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package leetcode.linkedList;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class AddTwoNumbersII_445 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ListNode cur1 = l1, cur2 = l2;
        while (cur1 != null) {
            stack1.push(cur1.val);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            stack2.push(cur2.val);
            cur2 = cur2.next;
        }
        int c = 0;
        ListNode result = new ListNode(0);
        while (!stack1.isEmpty() || !stack2.isEmpty() || c == 1) {
            int tmp = 0;
            if (stack1.isEmpty() && stack2.isEmpty())
                tmp = c;
            else if (stack1.isEmpty())
                tmp = c + stack2.pop();
            else if (stack2.isEmpty())
                tmp = c + stack1.pop();
            else
                tmp = stack1.pop() + stack2.pop() + c;
            ListNode node = new ListNode(tmp % 10);
            c = tmp / 10;
            node.next = result.next;
            result.next = node;
        }
        return result.next;
    }
}

删除链表中的节点

由于给出的是要删除的节点，无法获取其上一个节点，因此将其下一个节点的值复制过来，删除其下一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class DeleteNodeInALinkedList_237 {
    public void deleteNode(ListNode node) {
        if (node == null)
            return;
        if (node.next == null) {
            node = null;
            return;
        }
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

链表中删除一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveLinkedListElement_203 {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head, pre = dummy;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = pre.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

删除链表中离end第N的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveNthNodeFromEndOfList_19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode l = dummy;
        ListNode r =dummy;
        for (int i = 0; i < n + 1; i++) {
            r = r.next;
        }
        while (r != null) {
            l = l. next;
            r = r.next;
        }
        l.next = l.next.next;
        return dummy.next;
    }
}

链表排序问题

对一个链表进行插入排序

设置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
27
28
29
30
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class InsertionSortList_147 {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.next != null && cur.next.val < cur.val) {
                while (pre.next.val < cur.next.val)
                    pre = pre.next;
                ListNode tmp = cur.next;
                cur.next = cur.next.next;
                tmp.next = pre.next;
                pre.next = tmp;
                pre = dummy;
            }  else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

合并两个有序链表

百度二面遇到了,这个解法是设置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
27
28
29
30
31
32
33
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class MergeTwoSortedLists_21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode node1 = l1;
        ListNode node2 = l2;
        ListNode curr = dummy;
        while (node1 != null || node2 != null) {
            if (node1 == null) {
                curr.next = node2;
                break;
            } else if (node2 == null) {
                curr.next = node1;
                break;
            } else {
                if (node1.val <= node2.val) {
                    curr.next = node1;
                    node1 = node1.next;
                } else {
                    curr.next = node2;
                    node2 = node2.next;
                }
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}

归并排序

快慢指针将链表分为两部分，对两部分进行继续拆分，然后返回其合并结果。复杂度为O(NlogN)。

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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class SortList_148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head, slow = head;
        ListNode prev = null, left, right;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        left = sortList(head);
        right = sortList(slow);
        return mergeTwoList(left, right);
    }
    public ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        if (l1 != null)
            prev.next = l1;
        if (l2 != null)
            prev.next = l2;
        return dummy.next;
    }
}

链表调整问题

奇数前偶数后的问题

创建两个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
27
28
29
30
31
32
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class OddEvenLinkedList_328 {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode odd = new ListNode(0);
        ListNode even = new ListNode(0);
        ListNode lastOdd = odd;
        ListNode lastEven = even;
        ListNode cur = head;
        int i = 1;
        while (cur != null) {
            if (i % 2 == 0) {
                lastEven.next = cur;
                lastEven = lastEven.next;
            } else {
                lastOdd.next = cur;
                lastOdd = lastOdd.next;
            }
            cur = cur.next;
            i++;
        }
        lastEven.next = null;
        lastOdd.next = even.next;
        return odd.next;
    }
}

partion问题,将链表中小于target值的节点放在前面。解决思路还是两个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
27
28
29
30
31
32
33
package leetcode.linkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class PartitionList_86 {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null)
            return head;
        ListNode smaller = new ListNode(0);
        ListNode bigger = new ListNode(0);
        ListNode lastSmall = smaller;
        ListNode lastbig = bigger;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x){
                lastSmall.next = cur;
                lastSmall = lastSmall.next;
            }
            if (cur.val >= x) {
                lastbig.next = cur;
                lastbig = lastbig.next;
            }
            cur = cur.next;
        }
        lastbig.next = null;
        lastSmall.next = bigger.next;
        return smaller.next;
    }
}

将链表 L: L0→L1→…→Ln-1→Ln 变为 L0→Ln→L1→Ln-1→L2→Ln-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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RecordList_143 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = reverseList(slow.next);
        fast = slow.next;
        ListNode node = head;
        while (node != slow) {
            slow.next = fast.next;
            fast.next = node.next;
            node.next = fast;
            node = fast.next;
            fast = slow.next;
        }
    }
    private ListNode reverseList(ListNode head) {
        if (head == null)
            return head;
        ListNode p = head.next;
        head.next = null;
        while (p != null) {
            ListNode tmp = p;
            p = p.next;
            tmp.next = head;
            head = tmp;
        }
        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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveDuplicatesFromSortedList {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == pre.val)
                pre.next = cur.next;
            else {
                pre.next = cur;
                pre = pre.next;
            }
            cur = cur.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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveDuplicatesFromSortedListII_82 {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        boolean repeat = false;
        while(cur.next != null){
            if(cur.val == cur.next.val){
                repeat = true;
                cur = cur.next;
            } else {
                cur = cur.next;
                if(!repeat){
                    pre = pre.next;
                }
                pre.next = cur;
                repeat = false;
            }
        }
        if(repeat) pre.next = null;
        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
package leetcode.linkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ReverseLinkedList_206 {
    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;
    }
    /**
     * 创建一个链表
     * @param arr
     * @param n
     * @return
     */
    public static ListNode createLinkedList(int arr[], int n) {
        if (n == 0)
            return null;
        ListNode head = new ListNode(arr[0]);
        ListNode curNode = head;
        for (int i = 1; i < n; i++) {
            curNode.next = new ListNode(arr[i]);
            curNode = curNode.next;
        }
        return head;
    }
    public static void printLinkedList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }
        System.out.println("NULL");
    }
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5};
        int n = arr.length;
        ListNode head = createLinkedList(arr, n);
        printLinkedList(head);
        head = new ReverseLinkedList_206().reverseList(head);
        printLinkedList(head);
    }
}

反转指定位置的链表,解决思路，添加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
27
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ReverseLinkedListII_92 {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null)
            return null;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode pre= newHead;
        for (int i = 0; i < m-1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next = cur.next;
        for (int j = 0; j < n-m; j++) {
           cur.next = next.next;
           next.next = pre.next;
           pre.next = next;
           next = cur.next;
        }
        return newHead.next;
    }
}

以K个为一组来反转链表,添加dummy节点，K个节点处理一次，不足k个不处理

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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ReverseNodesInKGroup_25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        ListNode start = dummy;
        dummy.next = head;
        while (true) {
            ListNode node = start, cur, n = node;
            start = node.next;
            for (int i = 0; i < k && n != null; i++)
                n = n.next;
            if (n == null)
                break;
            for (int i = 0; i < k - 1; i++) {
                cur = node.next;
                node.next = cur.next;
                cur.next = n.next;
                n.next = cur;
            }
        }
        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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RotateLIst_61 {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode left = dummy, right = dummy, br = dummy;
        int length = 0;
        while (right.next != null) {
            length++;
            right = right.next;
        }
        for (int j = length - k%length; j> 0; j--)
            left = left.next;
        right.next = dummy.next;
        dummy.next = left.next;
        left.next = null;
        return dummy.next;
    }
}

成对交换节点, 添加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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class SwapNodewsInPairs_24 {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode node1, node2, next;
        while (pre.next != null && pre.next.next != null) {
            node1 = pre.next;
            node2 = node1.next;
            next = node2.next;
            node2.next = node1;
            node1.next = next;
            pre.next = node2;
            //靠后的一对节点
            pre = node1;
        }
        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
package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class PalindromeLinkedList_234 {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = reverseList(slow.next);
        fast = slow.next;
        ListNode node = head;
        while (fast != null) {
            if (node.val != fast.val)
                return false;
            node = node.next;
            fast = fast.next;
        }
        return true;
    }
    private ListNode reverseList(ListNode head) {
        if (head == null)
            return head;
        ListNode p = head.next;
        head.next = null;
        while (p != null) {
            ListNode tmp = p;
            p = p.next;
            tmp.next = head;
            head = tmp;
        }
        return head;
    }
}
Donate comment here