乐趣区

关于大数据:算法-链表操作题目套路

jiezi

0. 前言

简略的题目，然而没有练习过或者背过，可能反而也写不进去，在面试中往往是在短时间内就写完，你没有工夫画图，没有工夫推演，这些都只能在脑子里疾速实现，有时候拼了很久，感觉还是没有感觉，即便写进去了，在过后的一周到一个月照样会遗记，bug free 地写进去还是很费劲，作为对此深有体会的，或者跟我一样的有 99% 的人，像本文写的链表反转，如果能够在图上画进去，那你就肯定能够写的进去，因为边界很简略，相似有疾速排序荷兰国旗问题这些题目是国内面试级别上才会考的，比起像 flag 公司，还差那么一点，只管本人在算法方面不是很开窍，包含在校招时候也练过不少题，然而我晓得仍然很少，而且对题目没有记忆感，总感觉本人是个傻子，这么简略的题目，居然写不进去，不过仍然感觉考算法和数据结构的其实才是公司考核程序员最偏心最能考核思维的形式，说了这么多，包含自己在内，始终在身边各种算法大神碾压中，也期待在走向全栈工程师的路线上，单纯地从技术上，本人的算法和数据结构能越来越好把。

1. 经典题目，链表反转 

// 递归形式
public ListNode reverseList(ListNode head) {if (head == null || head.next == null)
      return head;
    ListNode next = head.next;
    ListNode new_head = reverseList(next);
    next.next = head;
    head.next = null;
    return new_head;
}
// 遍历
public ListNode reverseList(ListNode head) {

    ListNode pre = null, cur = head,next = null;
    while(cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

    return pre;
}

2. 相邻反转，局部反转 

// 反转相邻节点链表 1234 2143, 反转 5 个的也相似
public ListNode swapPairs(ListNode head) {if (head == null || head.next == null)
    return head;
  
  ListNode newNode = head.next;
  head.next = swapPairs(head.next.next);
  newNode.next = head;
  return newNode;
}

// 局部反转，12345 m=2 n=4 14325
public ListNode reverseBetween(ListNode head, int m, int n) {if (m>= n) return head;
  ListNode dump = new ListNode(0);
  dump.next = head;
  ListNode pre = dump;
  for (int i = 1; i< m; i++) {pre = pre.next;}
  
  head = pre.next;
  for (int i=m;i<n;i++) {
    ListNode nex = head.next;
    head.next = nex.next;
    next.next = pre.next;
    pre.next = nex;
  }
  
  return dump.next;
}

3. 链表求和 

// 两个链表求和
// 输出：(2 -> 4 -> 3) + (5 -> 6 -> 4)
// 输入：7 -> 0 -> 8
// 起因：342 + 465 = 807
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode resultListNode = new ListNode(0);
       ListNode current = resultListNode;
       int carry = 0;
       while(l1 !=null || l2 !=null){
           int sum = carry;
           if(l1!=null){
               sum += l1.val;
               l1 = l1.next;
           }
           if(l2!=null){
               sum += l2.val;
               l2 = l2.next;
           }
           int val = sum < 10?sum:sum - 10;
           carry = sum < 10 ?0:1;
           current.next = new ListNode(val);
           current =  current.next;
       }
        if(carry  == 1){current.next = new ListNode(1);
        }
        return resultListNode.next;
    }

吴邪，小三爷，混迹于后盾，大数据，人工智能畛域的小菜鸟。
更多请关注

退出移动版