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;
}
吳邪，小三爺，混跡于后臺，大資料，人工智能領域的小菜鳥，
更多請關注
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250083.html
標籤：其他