华为二面手撕代码leetcode中等难度链表题

华为上合面试二面手撕代码，给一个链表和一个数，将链表分为两部分，左边部分小于x，右边部分大于或等于x，保证两部分中节点的相对顺序与之前一致。 比如： Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5

这题我四个月前AC过，做得很大意当时没细想就AC了。由于手写和面试时间限制，一时之间又想不到自己从前的想法，很快有了思路写了下，大致是使用两个指针（当前最后一个小于x的节点和最后一个大于等于x的节点），不过还需要一个指针，保存第一个大于等于x的节点。遍历结束后，最后一个小于x的节点指向第一个大于等于x的节点。写完后，面试官就开始问别的问题，最后面试快结束让我讲一下思路。我就对着自己的代码讲。最后，面试官说专业二面通过了。聊得还行，面试官也很棒。说声谢谢，忐忑地等待三面。 其实，不见得是我的代码没问题，我觉得思路大致是对的，还是有些情况没有考虑：比如最后直接返回head，但没注意头节点必须为第一个小于x的节点；还比如最后一个大于等于x的节点要指向null。好在是手写，面试官也没太在意，放过我了，只是在我讲思路时，不时会对我翻白眼，当时我就在想为什么，好烦啊。现在终于知道了，这要是机考，就是重大BUG了。我还是太紧张了，抓到救命稻草（模糊的思路）就以为高枕无忧（代码AC），其实坑还挺多。不过手撕不比敲键盘，难受很多，我太难了。

严以律己，宽以待人！面试官仁慈，我要对自己要求高点。 把当时的思路复现，并且修改了BUG，时间和空间都是beats 100%，这就叫战胜自己！

public ListNode partition2(ListNode head, int x) {
          
   
        ListNode p = head;
        if(p == null) return head;
        ListNode lastMin = null;
        ListNode lastMax = null;ListNode firstMax = null;
        while(p!=null){
          
   
            if(p.val < x){
          
   
                 if(lastMin == null){
          
   
                     head = p;                     
                 }else{
          
   
                     lastMin.next = p;
                 }
                 lastMin = p;
            }
            else{
          
   
                 if(lastMax == null){
          
   
                     firstMax = p;
                 }else{
          
   
                     lastMax.next = p;
                 }
                 lastMax = p;
            }
            p = p.next;
        }
        if(lastMin != null)
        lastMin.next = firstMax;
        if(lastMax != null)
        lastMax.next = null;
        return head;
    }

完蛋！当时缺乏注释，过了四个月再来看我看不懂了。看了好久发现，当时的思路是模仿插入排序的思路，因为过了，所以没深究。发现代码有点小bug，又改了下，时间和空间都是beats 100%。小小地得意下。

public ListNode partition(ListNode head, int x) {
          
   
        ListNode p = head;
        ListNode pre = null;//ps pre
        ListNode gtxPre = null; // gtxs pre    
        ListNode gtx = null;
        if(p == null) return head;
        while(p!=null){
          
   
            if(p.val >= x){
          
   
               if(gtx == null){
          
   
                    gtx = p;
                    gtxPre = pre;
               }
               pre = p;
               p = p.next;
            }
            else if(p.val < x){
          
    
               if(gtx != null){
          
    //need to adjust nodes position
                    pre.next = p.next;
                    if(gtxPre != null){
          
   // gtx is not the head
                        gtxPre.next = p;
                    }
                    else{
          
   
                        head = p;
                    }
                    //摘下p，插入到gtx的前面
                    gtxPre = p;
                    p.next = gtx; 
               }else{
          
   
                   pre = p;
               }
               p = pre.next;
            }
        }
        return head;
    }

现在，也能对着自己的代码陶醉了，呵呵呵。 随便哪家，给个Offer吧~~