LeetCode解题报告—— Swap Nodes in Pairs & Divide Two Integers & Next Permutation

1. 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.

思路：模拟即可，思路不清楚时最好再纸上画画，确定节点指针的改变规则和顺序。交换顺序是这样的，用 cur 指针指向第一个，如果它不为空并且他的next也不为空则可以进行交换。交换时的步骤：(1)用temp暂存cur所指的第一个节点，(2)将cur指向第二个节点，也就是cur.next，（3）将第一个节点的next指向第二个节点的next，（4）第二个节点指向第一个节点，（5）将cur指向第三个节点，（6）这步容易忽略，要将改变后的第二个节点的next指向第四个节点(如果不为空的情况) 。这是因为一开始改变的时候，第一个节点前面没有节点，但是之后每个节点前面都是有节点的，所以之后不光要串连后面，还要串连前面。

public class Solution {

    public ListNode swapPairs(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode cur = head;

        ListNode newHead = head.next;

        while (cur != null && cur.next != null) {

            ListNode tmp = cur;

            cur = cur.next;

            tmp.next = cur.next;

            cur.next = tmp;

            cur = tmp.next;
　　　　　　// 第6步

            if (cur != null && cur.next != null) tmp.next = cur.next;

        }

        return newHead;

    }

}

2. Divide Two Integers

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.

思路：可以使用加法来实现除法，但这题要注意的是一些临界情况，比如正负，溢出，除数被为0等情况。试了下结果Time Limit exceeded，而且这里发现了一个很有意思的问题，java中Math.abs(-2147483648)的返回值应该是什么？。那么改进下这个想法，不是一个一个加除数，而是成倍的增加除数。比如对于10/1，原来的算法是 1+1+1+1+1+1+1+1+1+1 总共循环10次，

巴特西

LeetCode解题报告—— Swap Nodes in Pairs & Divide Two Integers & Next Permutation

最新文章

热门文章