链表

发表于 | 分类于

Leetcode

206. Reverse Linked List

Reverse a singly linked list.

解题思路：

翻转链表，三个指针pre, cur和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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        
        //当cur == null 时候，跳出循环，返回pre
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
}

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

解题思路：

画图！画图！画图！
搞清链表的拼接处的节点。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode preReverse = dummyHead;
        int cnt = n-m+1;    //统计翻转的次数
        
        //从虚拟头节点开始，找到翻转链表的前一个节点，需要m-1次
        while(--m != 0){
            preReverse = preReverse.next;
        }
        ListNode pre = null;
        ListNode cur = preReverse.next;
        //翻转链表，m节点开始
        while(cnt -- != 0){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //pre指向翻转链表的最后一个节点, cur指向最后节点的下一个节点
        // tailOfReverse 本来是翻转链表之前的第一个节点，存储在preReverse.next
        ListNode tailOfReverse = preReverse.next;
        tailOfReverse.next = cur;   //拼接翻转链表的尾部
        preReverse.next = pre;      //拼接翻转链表的头部
        return dummyHead.next;
    }
}

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

解题思路：

去除排序链表中重复的节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        
        ListNode pre = null;
        while(head != null){
            pre = head;
            head = head.next;
            //一直寻找，直到pre.val != head.val
            while(head != null && head.val == pre.val){
                head = head.next;
            }
            
            pre.next = head;
        }
        
        return dummyHead.next;
    }
}

86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

解题思路：

拼接两条链表的操作，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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyHead1 = new ListNode(-1);
        ListNode dummyHead2 = new ListNode(-1);
        ListNode cur1 = dummyHead1;
        ListNode cur2 = dummyHead2;
        
        while(head != null){
            if(head.val < x){
                cur1.next = head;
                cur1 = cur1.next;
            }
            else{
                cur2.next = head;
                cur2 = cur2.next;
            }
            head = head.next;
        }
        cur1.next = dummyHead2.next;	//拼接链表
        cur2.next = null;	//链表的尾部置为null，以防循环
        
        return dummyHead1.next;
    }
}

328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:

1
2
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:

1
2
The relative order inside both the even and odd groups should remain as it was in the input. 
The first node is considered odd, the second node even and so on ...

解题思路：

和上一道题目一模一样

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode dummyHeadOdd = new ListNode(-1);
        ListNode dummyHeadEven = new ListNode(-1);
        ListNode curOdd = dummyHeadOdd;
        ListNode curEven = dummyHeadEven;
        
        boolean odd = true;
        while(head != null){
            if(odd){
                curOdd.next = head;
                curOdd = curOdd.next;
            }
            else{
                curEven.next = head;
                curEven = curEven.next;
            }
            odd = !odd;
            head = head.next;
        }
        
        curEven.next = null;
        curOdd.next = dummyHeadEven.next;
        
        return dummyHeadOdd.next;
    }
}

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路：

把两条链表对应的值相加，得到的值的个位数创建新的节点，保留进位；
注意循环退出的条件

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0){
            int sum = 0;
            
            if(l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }
            
            sum += carry;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = cur.next;
            
            carry = sum / 10;
        }
        
        return dummyHead.next;
    }
}

445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

解题思路：

本道题目与上一题是类似的，只不过对于输入和输出都需要先翻转链表
然而题目步允许翻转链表，借助两个栈进行输入的翻转，
输出的链表使用往前插入，达到链表翻转的目的。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        while(l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        
        while(l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        
        int carry = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty() || carry != 0){
            int sum = carry;
            if(!stack1.isEmpty()){
                sum += stack1.pop();
            }
            if(!stack2.isEmpty()){
                sum += stack2.pop();
            }
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            node.next = dummyHead.next;
            dummyHead.next = node;
        }
        
        return dummyHead.next;
    }
}

203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example：

1
2
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

解题思路：

删除链表中特定的值，一个一个遍历，很简单；
注意更新pre节点的时机

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        
        while(head != null){
            if(head.val == val){
                pre.next = head.next;
            }
            else{
                pre = pre.next;
            }
            head = head.next;
        }
        
        return dummyHead.next;
    }
}

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example：

1
2
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

解题思路：

输入的链表是排序链表；
重复的节点全部删除，注意pre的处理

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode cur = head;
        
       while(cur != null){
           //若出现重复的数值，cur指向重复节点的最后一个
           while(cur.next != null && cur.val == cur.next.val){
               cur = cur.next;
           }
           //条件成立：cur是没有重复的节点, pre前进
           if(pre.next == cur){
               pre = cur;
           }
           //否则，cur目前是重复的节点, 跳过cur，并且pre不前进
           else{
               pre.next = cur.next;
           }
           //cur照常前进
           cur = cur.next;
       }
        
        return dummyHead.next;
    }
}

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example：

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解题思路：

合并链表

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        
        cur.next = l1 == null ? l2 : l1;
        
        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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }    
        if(l2 == null){
            return l1;
        }
        
        ListNode mergeNode = null;
        if(l1.val < l2.val){
            mergeNode = l1;
            mergeNode.next = mergeTwoLists(l1.next, l2);
        }
        else{
            mergeNode = l2;
            mergeNode.next = mergeTwoLists(l1, l2.next);
        }
        
        return mergeNode;
    }
}

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

解题思路：

四个指针，pre, node1, node2 和 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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        
        while(pre.next != null && pre.next.next != null){
            ListNode node1 = pre.next;
            ListNode node2 = pre.next.next;
            ListNode next = node2.next;
            
            pre.next = node2;
            node2.next = node1;
            node1.next = next;
            
            pre = node1;    //注意更新的节点pre
        }
        
        return dummyHead.next;
    }
}

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

example：

1
2
3
4
5
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

解题思路：

更新两个关键的节点，
一个是待翻转链表的前一个节点(PreOfReverse)
一个是链表翻转之后的尾节点，即未翻转链表的头节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = head;
        
        int total = 0;
        while(cur != null){
            ++total;
            cur = cur.next;
        }
        
        int times = total / k;
        cur = head;
        ListNode preOfReverse = dummyHead;  //翻转链表的前一个节点
        ListNode tailOfReverse = cur;       //尾节点，本来是第一个链表的头节点，翻转之后变尾节点
        while(times-- > 0){
            ListNode pre = preOfReverse;    //待翻转链表的前一个节点
            int cnt = k;
            //翻转链表操作
            while(cnt-- != 0){
                ListNode next = cur.next;
                cur.next = pre;
                
                pre = cur;
                cur = next;
            }
            
            //更新节点操作
            preOfReverse.next = pre;    
            tailOfReverse.next = cur;
            preOfReverse = tailOfReverse;
            tailOfReverse = cur;
        }
        
        return dummyHead.next;
    }
}

147. Insertion Sort List

Sort a linked list using insertion sort.

解题思路：

使用插入排序，每次取旧队列头节点，插入到新队列的合适位置，pre.val <= cur.val

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyHead = new ListNode(-1);  //新链表的虚拟头节点
        ListNode cur = head;    
        
        //依次遍历cur节点，将其插入到新链表中合适的位置
        while(cur != null){
            ListNode pre = dummyHead;
            ListNode next = cur.next;
            while(pre.next != null && pre.next.val < cur.val){
                pre = pre.next;
            }
            //将cur移到新链表，插入位置为pre和pre.next之间
            cur.next = pre.next;
            pre.next = cur;
            
            cur = next;
        }
        
        return dummyHead.next;
    }
}

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

解题思路：

归并排序链表

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        //不足一个节点，不需要再分割
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        ListNode middleTail = null;
        
        //切分两条链表
        while(fast != null && fast.next != null){
            middleTail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        middleTail.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        
        return merge(l1, l2);
    }
    
    //合并链表操作
    private ListNode merge(ListNode l1, ListNode l2){
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        
        cur.next = (l1 == null) ? l2 : l1;
        
        return dummyHead.next;
    }
}

237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

解题思路：

删除指定的节点，修改节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        if(node == null){
            return;
        }
        
        if(node.next == null){
            node = null;
        }
        
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

19. Remove Nth Node From End of List

Given a linked list, remove the n(th) node from the end of list and return its head.

Example：

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.
  After removing the second node from the end, the linked list becomes 1->2->3->5.

Note：
Given n will always be valid.
Try to do this in one pass.

解题思路：

双指针问题，注意preOfRemoveNode的位置，画图，枚举

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode p = dummyHead;
        ListNode preOfRemoveNode = dummyHead;
        
        // dummyHead -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        while(n-- != -1){
            p = p.next;    
        }
        
        while(p != null){
            p = p.next;
            preOfRemoveNode = preOfRemoveNode.next;
        }
        
        //验证preOfRemoveNode是否为尾节点
        if(preOfRemoveNode.next == null){
            preOfRemoveNode = null;
        }
        else{
            preOfRemoveNode.next = preOfRemoveNode.next.next;
        }
        
        return dummyHead.next;
    }
}

61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Example：

1
2
3
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

解题思路：

其实问题挺简单的，就是preOfRotateNode要找对了，还有节点tail

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || k == 0){
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode tail = dummyHead;
        
        //统计节点个数, 并保存尾节点
        int n = 0;
        while(tail.next != null){
            tail = tail.next;
            ++n;
        }
        
        //处理 k > n || k == 0 的情况
        k %= n;
        if(k == 0){
            return head;
        }
        
        ListNode preOfRotateNode = dummyHead;
        k = n - k;      //dummyHead -> 1 -> 2 -> 3 -> 4 -> null
        while(k-- != 0){
            preOfRotateNode = preOfRotateNode.next;
        }
        
        //旋转
        tail.next = dummyHead.next;
        dummyHead.next = preOfRotateNode.next;
        preOfRotateNode.next = null;
        
        return dummyHead.next;
    }
}

143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

解题思路：

分割链表，并重装

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null){
            return;
        }
        
        //链表一分为二
        ListNode fast = head;
        ListNode slow = head;
        ListNode middleTail = null;
        while(fast != null && fast.next != null){
            middleTail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        middleTail.next = null;         //第一条链表的尾后节点置位空
        ListNode l1 = head;             //假设l1 有 n 个节点
        ListNode l2 = reverse(slow);    //那么l2 有 n 个或者 n+1 个
        
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while(l1 != null){
            cur.next = l1;
            l1 = l1.next;
            
            cur.next.next = l2;
            l2 = l2.next;
            
            cur = cur.next.next;
        }
        cur.next = l2;      //l2可能还有1个节点
        
        head = dummyHead.next;
    }
    
    //翻转链表，并返回新链表的头节点
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
}

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up：
Could you do it in O(n) time and O(1) space?

解题思路：

解法与上一题一样

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        ListNode middleTail = null;
        while(fast != null && fast. next != null){
            middleTail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        middleTail.next = null;
        ListNode l1 = head;
        ListNode l2 = reverse(slow);
        
        while(l1 != null && l2 != null){
            if(l1.val != l2.val){
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        
        return true;
    }
    
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
}