给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
思路很简单,直接从最后一个结点逐渐指向第一个,并每次返回指向的第一个节点:
答案 1:
1 2 3 4 5 6 7 8 9 10
| class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode newNode = new ListNode(); newNode = reverseList(head.next); head.next.next = head; head.next = null; return newNode; } }
|
如果使用迭代,就得额外设置两个结点:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }
|
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路很简单,因为链表的定义是递归的,因此它的很多算法都可以用递归来做,因此这道题最好也是使用递归:
答案 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
while(list1 != null || list2 != null){ if(list1 == null){ return list2; }else if(list2 == null){ return list1; }else if(list1.val < list2.val){ list1.next = mergeTwoLists(list1.next, list2); return list1; }else { list2.next = mergeTwoLists(list1, list2.next); return list2; } } return null; } }
|
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
这里采用归并排序:
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
| struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) { if(!head1){ return head2; }else if(!head2){ return head1; }else if(head1->val < head2->val){ head1->next = merge(head1->next, head2); return head1; }else{ head2->next = merge(head1, head2->next); return head2; } }
struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) { if(head == NULL || head->next == NULL){ return head; } if(head->next == tail){ head->next = NULL; return head; } struct ListNode *slow = head, *fast = head; while (fast != tail) { slow = slow->next; fast = fast->next; if (fast != tail) { fast = fast->next; } } struct ListNode* mid = slow; return merge(toSortList(head, mid), toSortList(mid, tail)); }
struct ListNode* sortList(struct ListNode* head) { return toSortList(head, NULL); }
|