classSolution { public: voidmoveZeroes(vector<int>& nums){ int Left = 0, Right = 0; // Left的左边均为非零值,其指向第一个零值。Right的右边为未处理的序列,当前指向用于判断零值和非零值 for (int i = 0; i < nums.size(); ++i) { if (nums[i]) { swap(nums[Left], nums[Right]); // 交换位置 ++Left; } ++Right; } } };
1 2 3 4 5 6 7 8 9 10 11
classSolution: defmoveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ Left = Right = 0 for num in nums: if num: nums[Left], nums[Right] = nums[Right], nums[Left] Left += 1 Right += 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { publicvoidmoveZeroes(int[] nums) { intLeft=0; intRight=0; int temp; for (inti=0; i < nums.length; ++i) { if (nums[i] != 0) { temp = nums[Left]; nums[Left] = nums[Right]; nums[Right] = temp; ++Left; } ++Right; } } }
classSolution { public: ListNode* reverseList(ListNode* head){ ListNode *pre = nullptr; ListNode *next = nullptr; ListNode *cur = head; while (cur) { next = cur->next; // 先拿到后继结点 cur->next = pre; pre = cur; cur = next; } return pre; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public ListNode reverseList(ListNode head) { ListNodepre=null; ListNodenext=null; ListNodecur= head; while (cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } }
1 2 3 4 5 6 7 8 9 10
classSolution: defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: cur = head pre = None while cur: next = cur.next cur.next = pre pre = cur cur = next return pre
classSolution: defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: ifnot head ornot head.next: return head Last = self.reverseList(head.next) // 这里要用self head.next.next = head head.next = None return Last
五:回文链表
1. 数组
将链表中的数据复制到数组中,然后将数组反转或遍历第一个和最后一个数据进行比较
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: boolisPalindrome(ListNode* head){ vector<int> vals; while (head) { vals.emplace_back(head->val); head = head->next; } for (int i = 0, j = static_cast<int>(vals.size() - 1); i < j; ++i, --j) { if (vals[i] != vals[j]) returnfalse; } returntrue; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { publicbooleanisPalindrome(ListNode head) { List<Integer> vals = newArrayList<Integer>(); while (head != null) { vals.add(head.val); head = head.next; } for (inti=0, j = vals.size() - 1; i < j; ++i, --j) { if (vals.get(i) != vals.get(j)) returnfalse; } returntrue; } }
classSolution: defisPalindrome(self, head: Optional[ListNode]) -> bool: if (not head): returnTrue lastNode = self.reverseList(self.interMediateNode(head)) while (head != lastNode and head): if head.val != lastNode.val: returnFalse head = head.next lastNode = lastNode.next returnTrue
defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: cur = head pre = None while cur: next = cur.next cur.next = pre pre = cur cur = next return pre definterMediateNode(self, head: Optional[ListNode]) -> Optional[ListNode]: fastNode = head slowNode = head while fastNode and fastNode.next.next: fastNode = fastNode.next.next slowNode = slowNode.next return slowNode